Submission #1015806

#TimeUsernameProblemLanguageResultExecution timeMemory
1015806asli_bgKnapsack (NOI18_knapsack)C++11
73 / 100
1051 ms199760 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) x.begin(),x.end() #define fi first #define se second #define pb push_back #define sp <<' '<< typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vll; typedef vector<bool> vb; #define FOR(i,a) for(int i=0;i<(a);i++) #define FORE(i,a,b) for(int i=(a);i<(b);i++) #define RFOR(i,a) for(int i=(a);i>=0;i--) #define contp(a) for(auto el:a) {cout<<el.fi<<'-'<<el.se<<' ';}cout<<endl #define cont(a) for(auto el:a) {cout<<el<<' ';}cout<<endl const int MAXN=1e5+2; const int MAXS=2e3+2; int dp[MAXS]; set<pii,greater<pii>> say[MAXS][MAXS]; //say[i][j][x]=y; //i. weightte j.weigthe x.valuda olan elemandan y tane var signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,mxw; cin>>mxw>>n; vi v(n+1); vi w(n+1); vi k(n+1); FOR(i,n){ cin>>v[i+1]>>w[i+1]>>k[i+1]; } FOR(i,n){ say[0][w[i+1]].insert({v[i+1],k[i+1]}); } dp[0]=0; int ind; FORE(i,1,mxw+1){ ind=0; dp[i]=dp[i-1]; FORE(j,1,n+1){ if(i-w[j]>=0 and !say[i-w[j]][w[j]].empty()){ //kullan auto it=say[i-w[j]][w[j]].begin(); int val=(*it).fi; if(dp[i-w[j]]+val>dp[i]){ dp[i]=dp[i-w[j]]+val; ind=j; } } } if(ind>0){ FORE(j,1,n+1){ say[i][w[j]]=say[i-w[ind]][w[j]]; } auto it=say[i][w[ind]].begin(); int deg=(*it).fi; int tane=(*it).se; say[i][w[ind]].erase(*it); if(tane-1>0){ say[i][w[ind]].insert({deg,tane-1}); } } else{ FORE(j,1,n+1){ say[i][w[j]]=say[i-1][w[j]]; } } } cout<<dp[mxw]<<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...