Submission #4074558

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, W;
    cin >> N >> W;

    vector<vector<int>> val;
    val = vector<vector<int>>(4, vector<int>());
    int w0, v0;  cin >> w0 >> v0;
    val[0].push_back(v0);
    for(int i=1; i<N; i++){
        int w, v;  cin >> w >> v;
        val[w-w0].push_back(v);
    }
    for(int i=0; i<4; i++){
        sort(val[i].begin(), val[i].end(), greater<int>());
        for(int j=1; j<val[i].size(); j++){
            val[i][j] += val[i][j-1];
        }
    }

    int ans = 0;
    for(int a=0; a<=val[0].size(); a++) for(int b=0; b<=val[1].size(); b++) for(int c=0; c<=val[2].size(); c++) for(int d=0; d<=val[3].size(); d++){
        if(w0*a + (w0+1)*b + (w0+2)*c + (w0+3)*d > W) continue;
        
        int tmpVal = 0;
        if(a>0) tmpVal += val[0][a-1];
        if(b>0) tmpVal += val[1][b-1];
        if(c>0) tmpVal += val[2][c-1];
        if(d>0) tmpVal += val[3][d-1];
        ans = max(ans, tmpVal);
    }
    cout << ans << endl;
}

Submission Info

Judge Result