Submission #1535115
Source Code Expand
#include <bits/stdc++.h> #define int long long #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} int N,W; signed main(){ cin>>N>>W; int off = 0; vector<int> vs[4]; rep(i,N){ int w; cin>>w; if(i==0) off = w; w -= off; int v; cin>>v; vs[w].pb(v); } rep(i,4) sort(all(vs[i]),greater<int>()); int ans = 0; int vi = 0; rep(i,vs[0].size()+1){ if(i!=0) vi += vs[0][i-1]; int vj = 0; rep(j,vs[1].size()+1){ if(j!=0) vj += vs[1][j-1]; int vk = 0; rep(k,vs[2].size()+1){ if(k!=0) vk += vs[2][k-1]; int vl = 0; rep(l,vs[3].size()+1){ if(l!=0) vl += vs[3][l-1]; int wei = (off)*i + (off+1)*j + (off+2)*k + (off+3)*l; if(wei<=W){ int val = vi+vj+vk+vl; chmax(ans,val); } } } } } cout<<ans<<endl; }
Submission Info
Submission Time | |
---|---|
Task | D - Simple Knapsack |
User | sigma425 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1359 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 | 1 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 |