こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。
C++: paiza事務局作成コード Vol.3 O(DN)
通過テストケース数：3
実行時間(テストケース１)：0.01秒
実行時間(テストケース２)：0.01秒
実行時間(テストケース３)：1.01秒
#include <iostream>
#include <algorithm>
int main(void)
{
int N, D;
std::cin >> N >> D;
long *p = new long[N];
long m;
for( int i = 0 ; i < N ; i++ )
{
std::cin >> p[i];
}
std::stable_sort(p, p + N);
long ans, tmp;
long s, t;
bool flag;
for( int i = 0 ; i < D ; i++ )
{
std::cin >> m;
flag = true;
ans = 0;
s = 0;
t = N - 1;
while( s < t )
{
tmp = p[s] + p[t];
if( tmp > m ) t--;
else
{
if( ans < tmp ) ans = tmp;
s++;
}
}
std::cout << ans << std::endl;
}
delete[] p;
return 0;
}
C++: paiza事務局作成コード Vol.2 O(DNlogN)
通過テストケース数：２
実行時間(テストケース１)：0.01秒
実行時間(テストケース２)：0.05秒
実行時間(テストケース３)：--
#include <iostream>
#include <algorithm>
int main(void)
{
int N, D;
std::cin >> N >> D;
long *p = new long[N];
long m;
for( int i = 0 ; i < N ; i++ )
{
std::cin >> p[i];
}
std::stable_sort(p, p + N);
for( int i = 0 ; i < D ; i++ )
{
std::cin >> m;
int ans = 0;
for( int j = 0 ; j < N ; j++ )
{
int r = m - p[j];
int lb = 0, ub = N;
while( ub - lb != 1)
{
int mid = (ub + lb) / 2;
if( p[mid] <= r ) lb = mid;
else ub = mid;
}
ub--;
if( j >= ub ) continue;
if( p[ub] > r ) continue;
int s = p[j] + p[ub];
if( s <= m && ans < s )
{
ans = s;
}
}
std::cout << ans << std::endl;
}
delete[] p;
return 0;
}
C++: paiza事務局作成コード Vol.1 O(DN^2)
通過テストケース数：１
実行時間(テストケース１)：0.05秒
実行時間(テストケース２)：--
実行時間(テストケース３)：--
#include <iostream>
int main(void)
{
int N, D;
std::cin >> N >> D;
long *p = new long[N];
long m;
for( int i = 0 ; i < N ; i++ )
{
std::cin >> p[i];
}
for( int i = 0 ; i < D ; i++ )
{
std::cin >> m;
int ans = 0;
for( int j = 0 ; j < N ; j++ )
{
for( int k = j + 1 ; k < N ; k++ )
{
int s = p[j] + p[k];
if( s > m ) continue;
if( ans < s ) ans = s;
}
}
std::cout << ans << std::endl;
}
delete[] p;
return 0;
}
