#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <memory>
#include <chrono>
using namespace std::chrono;

template<int MAX_N>
milliseconds solve(bool showcomb, bool showres);

int main()
{
  // 乱数初期設定等の時間と表示時間を無視するために計算中の時間のみ計測する
  // 結果のみ出力する
  auto s = solve<5000>(false, true);
  std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;

  s = solve<10000>(false, true);
  std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;

  s = solve<15000>(false, true);
  std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;

  s = solve<20000>(false, true);
  std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;
}

template<int MAX_N>
milliseconds solve(bool showcomb, bool showres)
{
  std::mt19937 engine(system_clock::now().time_since_epoch().count());
  std::uniform_int_distribution<int> dis(1, 9);

  constexpr int MAX_W = MAX_N * 2;
  constexpr int W     = MAX_W + 1;

  std::vector<int>  dp( (MAX_N + 1)*(MAX_W + 1) );
  std::vector<bool> bp( (MAX_N + 1)*(MAX_W + 1) );
  std::vector<int>  w( (MAX_N + 1) );
  std::vector<int>  v( (MAX_N + 1) );
  std::vector<int>  sel;

  for (int i = 1; i < MAX_N + 1; i++) {
    w[i] = dis(engine);
    v[i] = dis(engine);
  }

  // ここから時間測定する
  auto p = system_clock::now();

  std::fill(bp.begin(),bp.begin()+MAX_W+1,true);

  for (int i = 1; i <= MAX_N; i++) {
    for (int j = 1; j <= MAX_W; j++) {
        if ((w[i] <= j)  && (v[i] + dp[(i-1)*W + j - w[i]]) > dp[ (i - 1) * W + j]) {
          dp[i*W + j] = v[i] + dp[(i - 1)*W + j - w[i]];
          bp[i*W + j] = true;
        } else {
          dp[i*W + j] = dp[(i - 1) * W + j];
          bp[i*W + j] = false;
        }
    }
  }

  int maxValue = dp[MAX_N*W + MAX_W], maxWeight = 0;
  int wt = MAX_W;

  for (int i = MAX_N; i >= 1; i--)
    if (bp[i*W  + wt]) {
      sel.emplace_back(i);
      wt -= w[i];
      maxWeight += w[i];
    }

  std::reverse(std::begin(sel), std::end(sel));

  // ここまでの経過時間を取得
  auto s = duration_cast<milliseconds>(system_clock::now() - p);

  if (showcomb) {
    for (int i = 0; i < static_cast<int>(sel.size()); i++) {
      std::cout << "(" << w[sel[i]] << "," << v[sel[i]] << ")";
      if (!((i + 1) % 10))
        std::cout << std::endl;
    }
    std::cout << std::endl;
  }

  if (showres)
    std::cout << "Answer : number = " << MAX_N << ", weight = " << maxWeight << ", value = " << maxValue << std::endl;

  return s;
}