Submission #4075263
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; ll n, w, w1, bufw, wv[4][100], c[4]; int main() { cin >> n >> w; for(ll i = 0; i < 4; i++){wv[i][0] = 0; c[i] = 0;} cin >> w1 >> wv[0][1]; c[0]++; for(ll i = 1; i < n; i++){ cin >> bufw; cin >> wv[bufw-w1][++c[bufw-w1]]; } for(ll i = 0; i < 4; i++){sort(wv[i]+1, wv[i]+c[i]+1, greater<>());} for(ll i = 0; i < 4; i++){for(ll j = 1; j <= c[i]; j++){wv[i][j] += wv[i][j-1];}} ll vmax = 0; for(ll i = 0; i <= c[0] && i*w1 <= w; i++){ for(ll j = 0; j <= c[1] && i*w1 + j*(w1+1) <= w; j++){ for(ll k = 0; k <= c[2] && i*w1 + j*(w1+1) + k*(w1+2) <= w; k++){ for(ll l = 0; l <= c[3] && i*w1 + j*(w1+1) + k*(w1+2) + l*(w1+3) <= w; l++){ vmax = max(wv[0][i]+wv[1][j]+wv[2][k]+wv[3][l], vmax); } } } } //for(ll i = 0; i < 4; i++){for(ll j = 0; j <= c[i]; j++){cout << wv[i][j];}cout << endl;} cout << vmax; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | divinediscon10t |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1012 Byte |
Status | AC |
Exec Time | 1 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 | 1 ms | 256 KB |
quarter1 | AC | 1 ms | 256 KB |
quarter2 | AC | 1 ms | 256 KB |
rand0 | AC | 1 ms | 256 KB |
rand1 | AC | 1 ms | 256 KB |
rand2 | AC | 1 ms | 256 KB |
smallw0 | AC | 1 ms | 256 KB |
smallw1 | AC | 1 ms | 256 KB |
smallw2 | AC | 1 ms | 256 KB |