Perl TLE solution for http://codeforces.com/contest/269/problem/B

B. Greenhouse Effect-AC.pl

#!perl
use v5.18;
# time complexity: O(Nlog(N))
# got Accepted
while(<>){
    my(@b,@a,$i,$n,$m,$s0,$pos);
    ($n,$m)=split;
    for $i ( 0..$n-1 ) {
        ($s0,$_)=split ' ',<>; push @a,$s0;
    }
    $b[0]=$a[0];
    for $i ( 1..$#a ){
        $pos=upper_bound($a[$i], \@b);
        if ($pos == @b) {push @b, $a[$i];}
        else {$b[$pos] = $a[$i];}
    }
    say $n-@b;
}

#find the first more than $num;
sub upper_bound {
    my ($num,$array)=@_;
    my ($i,$high,$low,$mid);
    $low = -1; $high = $#{$array};
    while($low+1 < $high) {
        $mid=$low + int(($high-$low)/2);
        if($array->[$mid] > $num) {$high=$mid;}
        else {$low=$mid;}
    }
    return $array->[$high]<=$num ? scalar @$array : $high;
}

B. Greenhouse Effect-TLE.pl

#!perl
# got Time limit exceeded. ;-(
use strict;
use warnings;
my($n,$m,@s);
$_=<>;

($n,$m)=split;
@s=();
my($i,@x,$s0,$x0,@dp,$result);
for $i ( 0..$n-1 ) {
    ($s0,$x0)=split ' ',<>;
    push @s,$s0;
    $dp[$i]=1;
}
$result=1;
for $i ( 1..$n-1 ) {
    for my $j ( 0..$i-1 ) {
        if ($s[$j]<=$s[$i] && $dp[$j]+1>$dp[$i]) {
            $dp[$i]=$dp[$j]+1;
            $result=$dp[$i]if($dp[$i]>$result);
        }
    }
}
print$n-$result,"\n";