http://paiza.jp/poh/ec-campaign/result/d46256a3f3e319a2c0954ead2e4d21cd 0.01 / 0.01 / 0.18

gistfile1.txt

use strict;
use warnings;

my $PRICE_MAX = 1_000_000;
my $PRICE_MIN = 10;
my $ALGORITHM_SWITCH_THRESHOLD = 1000; # TODO: 適当に決めるな馬鹿

my @lines = split "\n", do { local $/; <> };
my ( $num_products, undef ) = split( " ", shift(@lines) );
my @prices = splice( @lines, 0, $num_products );
if ( $ALGORITHM_SWITCH_THRESHOLD < $num_products ) {
    histogram_based( \@prices, \@lines );
}
else {
    sorted_array_based( \@prices, \@lines );
}

sub sorted_array_based {
    my ($prices, $campaigns) = @_;
    my @prices = sort { $a <=> $b } @$prices;

    my $idx_of_max_in = sub {
        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;
    };

    DAY: for my $target ( @$campaigns ) {
        my $head_idx = 0;
        my $tail_idx = $prices[-1] < $target - $prices[0]
            ? scalar(@prices) - 1
            : $idx_of_max_in->( \@prices, 0, scalar @prices - 1, $target - $prices[0] );
        my $best = 0;
        FIND: while ( $head_idx < $tail_idx ) {
            my $sum = $prices[$head_idx] + $prices[$tail_idx];
            if ( $sum == $target ) {
                $best = $target;
                last FIND;
            }
            elsif ( $sum < $target ) {
                $best = $sum if $best < $sum;
                $head_idx++;
            }
            else {
                $tail_idx--;
            }
        }
        print $best, "\n";
    }
}

sub histogram_based {
    my ($prices, $campaigns) = @_;
    my @hist;
    map { $hist[$_]++ } @$prices;

    my @sorted;
    my $sorted_max = $PRICE_MIN - 1;

    DAY: for my $target ( @$campaigns ) {
        my $best = 0;
        my $idx = 0;
        my $last_val = 0;
        my $search_range = $PRICE_MAX;
        HEAD: while (1) {
            my $val = $sorted[$idx];
            unless ( $val ) {
                do { $sorted_max++ } while !$hist[$sorted_max] && $sorted_max < $PRICE_MAX;
                last HEAD if $sorted_max == $PRICE_MAX;
                $val = $sorted[$idx] = $sorted_max;
            }

            my $tail_target = $target - $val;
            last HEAD if $tail_target < $val;
            TAIL: for my $gap ( 0..$search_range ) {
                if ( $hist[$tail_target - $gap] ) {
                    if ( $tail_target - $gap != $val || $hist[$val] > 1 ) {
                        $best = $target - $gap;
                        last HEAD unless $gap;
                        $search_range = $gap - 1;
                        last TAIL;
                    }
                }
            }
            $idx++;
        }
        print $best, "\n";
    }
}