Submission #3766476

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define fore(i, x, a) for(auto &&x:a) 
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
#define F first
#define S second
const int inf=1001001001;
const long long INF=1001001001001001001;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vii = vector<int>;
using vll = vector<ll>;
using priority_queue_small = priority_queue<int, vector<int>, greater<int> >;
template<class T>using vv = vector<T>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T>T gcd(T a, T b){ return b ? gcd(b, a % b) : a; }
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
int dy[]={0, 1, -1, 0};
int dx[]={1, 0, 0, -1};

int n, W;
int main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
  cin >> n >> W;
  vll w(n), v(n);
  rep(i, 0, n) cin >> w[i] >> v[i];
  ll bottom = *min_element(ALL(w));
  vll item[4];
  rep(i, 0, n) {
    item[w[i] - bottom].pb(v[i]);
  }
  rep(i, 0, 4) {
    sort(ALL(item[i]), greater<int>());
    item[i].insert(item[i].begin(), 0);
    rep(j, 0, item[i].size()) 
      item[i][j+1] += item[i][j];
  }
  ll ans = 0;
  rep(a, 0, item[0].size()) {
    rep(b, 0, item[1].size()) {
      rep(c, 0, item[2].size()) {
        rep(d, 0, item[3].size()) {
          ll weight = 0, val = 0;
          weight += a * bottom;
          val += item[0][a];
          weight += b * (bottom + 1);
          val += item[1][b];
          weight += c * (bottom + 2);
          val += item[2][c];
          weight += d * (bottom + 3);
          val += item[3][d];
          if (weight <= W) ans = max(ans, val);
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Judge Result