gistfile1.pl

use strict;
use warnings;

# find the most greater value in range of less or equal to given target.
# returns the index of that value.
# array must be ascend sorted.
sub idx_of_max_in {
    my ( $array, $head, $tail, $target ) = @_;
    return $tail if $array->[$tail] <= $target;
    return $head if $array->[$head] == $target;
    while ( $head <= $tail ) {
        my $where = int( ( $head + $tail ) / 2 );
        if ( $array->[$where] == $target ) {
            return $where;
        }
        elsif ( $target < $array->[$where] ) {
            $tail = $where - 1;
        }
        else {
            $head = $where + 1;
        }
    }
    return $head - 1;
}

my @lines = split "\n", do { local $/; <> };
my ( $num_prices, undef ) = split( " ", shift(@lines) );
my @prices = splice ( @lines, 0, $num_prices );

sub array_based {
    @prices = sort { $a <=> $b } @prices;
    my $price_max_idx = $num_prices - 1;
    my $min_price = $prices[0];
    my $min_pair_price = $prices[0] + $prices[1];
    my $binsearch_limit = $prices[0] + $prices[-1];
    my @results;

    DAY: for my $target (@lines) {
        $target = int($target);

        # short cut for exceptional situation
        if ( $min_pair_price > $target ) {
            push @results, 0;
            next DAY;
        }

        # find most expensive price in which cheeper than target price
        # with using binary search
        my ( $head, $tail ) = ( 0, $price_max_idx );
        if ( $target < $binsearch_limit ) {
            $tail = idx_of_max_in( \@prices, $head, $tail, $target - $min_price );
        }

        my $best = 0;
        PRODUCT: while (1) {
            my $tail_val = $prices[$tail];
            my $head_target = $target - $tail_val;
            my ( $head_val, $head_next_val ) = ( $prices[$head], $prices[$head+1] );
            while ( $head_next_val <= $head_target && $head < $tail ) {
                ( $head_val, $head_next_val ) = ( $head_next_val, $prices[++$head] );
            }
            my $val = $head_val + $tail_val;
            if ( $best < $val && $val <= $target ) {
                $best = $val;
                last PRODUCT if $best == $target;
            }
            $tail--;
            last PRODUCT unless $head < $tail;
        }
        push @results, $best;
    }
    my $res = join( "\n", @results );
    print $res, "\n";

}


sub hist_based {
    my @hist;
    $hist[$_]++ for @prices;
    my @low_ends;
    for ( 0..500 ) {


        push @low_ends, $_ if $hist[$_];
    }

    my @results;
    DAY: for my $target ( @lines ) {
        my $tail = $target;
        my $best = 0;
        my $low_head = 0;
        PRODUCT: while (1) {
            do { $tail-- } while !$hist[$tail] && $tail;
            last PRODUCT unless $tail;
            my $head_target = $target - $tail;
            last PRODUCT if $tail < $head_target;
            next PRODUCT if $head_target == $tail && $hist[$tail] < 2;

            if ( $head_target < $low_ends[-2] ) {
                $low_head++ while $low_ends[$low_head + 1] <= $head_target;
                my $head = $low_ends[$low_head];
                if ( $best < $head + $tail && $head + $tail <= $target) {
                    $best = $head + $tail;
                    last PRODUCT if $best == $target;
                }
            }
            else {

                my $head = $head_target;

                $head-- while !$hist[$head] && $head;
                next PRODUCT unless $head;
                if ( $head + $tail > $target ) {
                    next PRODUCT;
                }
                if ( $best < $head + $tail ) {
                    $best = $head + $tail;
                    last PRODUCT if $best == $target;
                }
            }
        }
        push @results, $best;
    }

    my $res = join( "\n", @results );
    print $res, "\n";

}
$num_prices > 10000 ? hist_based() : array_based();