Submission #3728175

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int memo[4];

int main() {
  int n, W;
  cin >> n >> W;
  vector<vector<ll>> vv(4);
  for (int i = 0; i < n; ++i) {
    int w, v;
    cin >> w >> v;
    vv[w % 4].push_back(v);
    memo[w % 4] = w;
  }
  for (int i = 0; i < 4; ++i) {
    sort(vv[i].rbegin(), vv[i].rend());
    for (int j = 1; j < vv[i].size(); ++j) {
      vv[i][j] += vv[i][j - 1];
    }
  }
  for (int i = 0; i < 4; ++i) {
    vv[i].insert(vv[i].begin(), 0);
  }
  ll ans = 0;
  for (int i = 0; i < vv[0].size(); ++i) {
    for (int j = 0; j < vv[1].size(); ++j) {
      for (int k = 0; k < vv[2].size(); ++k) {
        for (int l = 0; l < vv[3].size(); ++l) {
          if (memo[0] * i + memo[1] * j + memo[2] * k + memo[3] * l <= W) {
            ans = max(ans, vv[0][i] + vv[1][j] + vv[2][k] + vv[3][l]);
          }
        }
      }
    }
  }
  cout << ans << endl;
}

Submission Info

Judge Result