Submission #4074573
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ int N; ll W; cin >> N >> W; vector<vector<int>> val; val = vector<vector<int>>(4, vector<int>()); ll 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(ll a=0; a<=val[0].size(); a++) for(ll b=0; b<=val[1].size(); b++) for(ll c=0; c<=val[2].size(); c++) for(ll 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
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | yapoo |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1063 Byte |
Status | AC |
Exec Time | 2 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3 |
All | antigreedy0, antigreedy1, antigreedy2, example0, example1, example2, example3, quarter0, quarter1, quarter2, rand0, rand1, rand2, smallw0, smallw1, smallw2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
antigreedy0 | AC | 1 ms | 256 KB |
antigreedy1 | AC | 1 ms | 256 KB |
antigreedy2 | AC | 1 ms | 256 KB |
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
example3 | AC | 1 ms | 256 KB |
quarter0 | AC | 2 ms | 256 KB |
quarter1 | AC | 2 ms | 256 KB |
quarter2 | AC | 2 ms | 256 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 2 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |
smallw0 | AC | 2 ms | 256 KB |
smallw1 | AC | 2 ms | 256 KB |
smallw2 | AC | 2 ms | 256 KB |