Submission #1015832

#TimeUsernameProblemLanguageResultExecution timeMemory
1015832asli_bgKnapsack (NOI18_knapsack)C++11
73 / 100
1079 ms47496 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]; vii vec[MAXS]; //vec[i]--> i.weightte olan valueları farklı elemanları //max value ya göre sortla pii say[MAXS][MAXS]; //say[i][j]={x,y}; //i. weightte j.weigthe x.valuda olan elemandan y tane var ///y=0 olunca bir sonrakine gec int ok[MAXS][MAXS]; //ok[i][j]=x; //i. weightte j.weigthe x.elemandayız bool mycmp(pii a,pii b) { return a.fi>b.fi; } 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){ vec[w[i+1]].pb({v[i+1],k[i+1]}); } FOR(i,n){ sort(all(vec[w[i+1]]),mycmp); say[0][w[i+1]]=vec[w[i+1]][0]; ok[0][w[i+1]]=0; } 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]].se!=0){ //kullan //cout<<"sz "<<say[i-w[j]][w[j]].se<<endl; int val=say[i-w[j]][w[j]].fi; if(dp[i-w[j]]+val>dp[i]){ dp[i]=dp[i-w[j]]+val; ind=j; } } } if(ind>0){ FORE(j,1,mxw+1){ say[i][j]=say[i-w[ind]][j]; ok[i][j]=ok[i-w[ind]][j]; } int temp=--say[i][w[ind]].se; if(!temp) { ok[i][w[ind]]++; if(ok[i][w[ind]]<(int) vec[w[ind]].size()){ say[i][w[ind]]=vec[w[ind]][ok[i][w[ind]]]; } } } else{ //kullanmadım FORE(j,1,mxw+1){ say[i][j]=say[i-1][j]; ok[i][j]=ok[i-1][j]; } } } //FOR(i,mxw+1) cout<<dp[i]<<' '; //cout<<endl; 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...