こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。
Perl: paiza事務局作成コード Vol.3 O(DN)
通過テストケース数：3
実行時間(テストケース１)：0.02秒
実行時間(テストケース２)：0.33秒
実行時間(テストケース３)：10.02秒
$line1 = <STDIN>;
@line1 = split(/ /, $line1);
$N = $line1[0];
$D = $line1[1];
@p;
for( $i = 0 ; $i < $N ; $i++)
{
$p[$i] = <STDIN>;
}
@p = sort { $a <=> $b } @p;
for( $i = 0 ; $i < $D ; $i++ )
{
$m_j = <STDIN>;
$ans = 0;
$flag = 1;
$s = 0;
$t = $N - 1;
while( $s < $t )
{
$tmp = $p[$s] + $p[$t];
if( $tmp > $m_j )
{
$t--;
}
else
{
if( $ans < $tmp )
{
$ans = $tmp;
}
$s++;
}
}
print "$ans\n";
}
Perl: paiza事務局作成コード Vol.2 O(DNlogN)
通過テストケース数：２
実行時間(テストケース１)：0.22秒
実行時間(テストケース２)：6.38秒
実行時間(テストケース３)：--
$line1 = <STDIN>;
@line1 = split(/ /, $line1);
$N = $line1[0];
$D = $line1[1];
@p;
for( $i = 0 ; $i < $N ; $i++)
{
$p[$i] = <STDIN>;
}
@p = sort { $a <=> $b } @p;
for( $i = 0 ; $i < $D ; $i++ )
{
$m_j = <STDIN>;
$ans = 0;
for( $j = 0 ; $j < $N ; $j++ )
{
$r = $m_j - $p[$j];
$lb = 0, $ub = $N;
while( $ub - $lb != 1 )
{
$mid = int(($ub + $lb) / 2);
if( $p[$mid] <= $r )
{
$lb = $mid;
}
else
{
$ub = $mid
}
}
$ub--;
if( $j >= $ub )
{
next;
}
if( $p[$ub] > $r )
{
next;
}
$tmp = $p[$j] + $p[$ub];
if( $tmp <= $m_j && $ans < $tmp )
{
$ans = $tmp;
}
}
print "$ans\n";
}
Perl: paiza事務局作成コード Vol.1 O(DN^2)
通過テストケース数：１
実行時間(テストケース１)：6.46秒
実行時間(テストケース２)：--
実行時間(テストケース３)：--
$line1 = <STDIN>;
@line1 = split(/ /, $line1);
$N = $line1[0];
$D = $line1[1];
@p;
for( $i = 0 ; $i < $N ; $i++)
{
$p[$i] = <STDIN>;
}
for( $i = 0 ; $i < $D ; $i++ )
{
$m_j = <STDIN>;
$ans = 0;
for( $j = 0 ; $j < $N ; $j++ )
{
for( $k = $j + 1 ; $k < $N ; $k++ )
{
$tmp = $p[$j] + $p[$k];
if( $tmp > $m_j )
{
next;
}
if( $ans < $tmp )
{
$ans = $tmp;
}
}
}
print "$ans\n";
}
