POH! Vol.1 C++模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

C++: paiza事務局作成コード Vol.3 O(DN)

通過テストケース数:3
実行時間(テストケース1):0.01秒
実行時間(テストケース2):0.01秒
実行時間(テストケース3):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)

通過テストケース数:2
実行時間(テストケース1):0.01秒
実行時間(テストケース2):0.05秒
実行時間(テストケース3):--

#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)

通過テストケース数:1
実行時間(テストケース1):0.05秒
実行時間(テストケース2):--
実行時間(テストケース3):--

#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;
}
ページの先頭へ戻る