Submission #2411708

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  long long n, w;
  cin >> n >> w;
  vector<long long> v[4];
  long long w1;
  for (int i = 0; i < n; i++) {
    long long a, b;
    cin >> a >> b;
    if (i == 0) w1 = a;
    v[a-w1].push_back(-b);
  }
  for (int i = 0; i < 4; i++) {
    sort(v[i].begin(), v[i].end());
  }

  long long ans = 0;

  long long t = w;
  long long tv = 0;
  for (int i = 0; i <= v[0].size(); i++) {
    long long p = t;
    long long pv = tv;
    for (int j = 0; j <= v[1].size(); j++) {
      long long q = p;
      long long qv = pv;
      for (int k = 0; k <= v[2].size(); k++) {
        long long r = q;
        long long rv = qv;
        for (int l = 0; l <= v[3].size(); l++) {
          r -= w1+3;
          if (r < 0 || l == v[3].size()) {
            ans = max(ans, -rv);
            break;
          }
          rv += v[3][l];
        }
        q -= w1+2;
        if (q < 0 || k == v[2].size()) {
          ans = max(ans, -qv);
          break;
        }
        qv += v[2][k];
      }
      p -= w1+1;
      if (p < 0 || j == v[1].size()) {
        ans = max(ans, -pv);
        break;
      }
      pv += v[1][j];
    }
    t -= w1;
    if (t < 0 || i == v[0].size()) {
      ans = max(ans, -tv);
      break;
    }
    tv += v[0][i];
  }

  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result