Submission #2245582

---

Source Code Expand

#include <algorithm>
#include <array>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);

  int N, W, w[111] = {0}, v[111], w0, sp = 0;

  std::cin >> N >> W >> w0 >> v[0];
  
  for (int i = 1; i < N; i ++) {
    std::cin >> w[i] >> v[i];

    w[i] -= w0;
  }

  for (int t = 0; t <= N; t ++) {
    if (t * w0 > W)
      break;

    int r = W - t * w0;

    int dp[2][333][111];

    auto curr = dp[0], next = dp[1];

    memset(curr, -1, sizeof(dp[0]));

    curr[0][0] = 0;

    for (int i = 0; i < N; i ++) {
      memset(next, -1, sizeof(dp[0]));
      
      for (int j = 0; j < 333; j ++) {
        for (int k = 0; k <= t; k ++) {
          if (curr[j][k] < 0)
            continue;

          next[j][k] = std::max(curr[j][k], next[j][k]);
          
          if (j + w[i] <= r && k < t)
            next[j + w[i]][k + 1] = std::max(curr[j][k] + v[i], next[j + w[i]][k + 1]);
        }
      }
      
      std::swap(curr, next);
    }

    for (int j = 0; j < 333; j ++)
      for (int k = 0; k <= t; k ++)
        if (curr[j][k] > sp)
          sp = curr[j][k];
  }

  std::cout << sp << std::endl;

  return 0;
}

Submission Info

Judge Result