Submission #1264978

#TimeUsernameProblemLanguageResultExecution timeMemory
1264978avohadoKnapsack (NOI18_knapsack)C++20
100 / 100
75 ms18524 KiB
#include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define maxn 200005 #define f first #define s second #define ll long long #define pb(x) push_back(x) #define all(v) v.begin(), v.end() void solve(){ int s, n; cin >> s >> n; vector<pair<int, int>> v[s+1]; int x[n], w[n], k[n]; for(int i=0; i<n; i++){ cin >> x[i] >> w[i] >> k[i]; v[w[i]].push_back({x[i], k[i]}); } for(int i=1; i<=s; i++){ sort(all(v[i])); } int dp[s+1][s+1]; for(int i=0; i<=s; i++){ dp[0][i]=0; } for(int j=0; j<=s; j++){ dp[j][0]=0; } for(int i=1; i<=s; i++){ for(int j=1; j<=s; j++){ dp[i][j]=dp[i][j-1]; int i1=v[j].size()-1, j1=1; if((int)v[j].size()<1){ continue; } int ck=j, sum=v[j][v[j].size()-1].f; while(ck<=i){ dp[i][j]=max(dp[i][j], dp[i-ck][j-1]+sum); ck+=j; if(j1==v[j][i1].s){ i1--; if(i1<0){ break; } j1=1; }else{ j1++; } sum+=v[j][i1].f; } } } cout << dp[s][s]; } int main(){ cin.tie(nullptr)->sync_with_stdio(0); int t=1; //cin >> t; while(t--){ solve(); cout << "\n"; } return 0; }
#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...