제출 #1195327

#제출 시각아이디문제언어결과실행 시간메모리
1195327lukasuliashviliKnapsack (NOI18_knapsack)C++17
17 / 100
13 ms23880 KiB
// Source: https://usaco.guide/general/io #include <bits/stdc++.h> using namespace std; #define int long long #define rep(i,a,b) for(int i=a; i<=b; i++) #define fs first #define sc second #define pb push_back const int N=1e6+3; const int R=2002; int a[N],v[N],w[N],k[N],dp[N]; vector<pair<int,int>> vec[N],vec1; signed main(){ int n,s; cin>>s>>n; rep(i,1,n){cin>>v[i]>>w[i]>>k[i]; vec[w[i]].pb({v[i],k[i]});} rep(i,1,s){ sort(vec[i].begin(),vec[i].end()); reverse(vec[i].begin(),vec[i].end()); for(int j=0; j<vec[i].size(); j++){ int sum=0,pow=1; int k1=vec[i][j].sc; int v1=vec[i][j].fs; while(sum<s and k1){ sum+=pow*i; k1-=pow; if(k1<0) break; vec1.pb({pow*i,pow*v1}); pow++; } } for(int i1=0; i1<vec1.size(); i1++){ for(int j1=s; j1>=vec1[i1].fs; j1--){ dp[j1]=max(dp[j1],dp[j1-vec1[i1].fs]+vec1[i1].sc); } } vec1.clear(); } // for(auto x:vec){ // cout<<x.fs<<" "<<x.sc<<" "<<endl; // } // for(int kl=1; kl<=n; kl++){ // for(int i=0; i<vec[kl].size(); i++){ // for(int j=s; j>=vec[kl][i].sc; j--){ // dp[j]=max(dp[j-vec[kl][i].sc]+vec[kl][i].fs,dp[j]); // } // } // } cout<<dp[s]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...