Submission #1210674

#TimeUsernameProblemLanguageResultExecution timeMemory
1210674ASGA_RedSeaKnapsack (NOI18_knapsack)C++20
29 / 100
8 ms652 KiB
/** * بسم الله الرحمن الرحيم * ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿ */ /// author : "ASGA" #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; using ll=long long; signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int s,n;cin>>s>>n; vector<ll>d(s+1,0); while(n--){ ll v,w,k;cin>>v>>w>>k; k=min(k,s/w); vector<multiset<ll>>a(w); vector<ll>vv(s+1,0); for(int i=0;i<=s;i++){ vv[i]=v*((s-i+w)/w); } for(int i=s;i>=0;i--){ ll sz=a[i%w].size(); if(sz<k)a[i%w].insert(d[i]+vv[i]); } vector<ll>cnt(w,0); for(int i=s;i>=w;i--){ a[i%w].erase(a[i%w].find(d[i]+vv[i])); if(i>=w*k){a[i%w].insert(d[i-w*k]+vv[i-w*k]);cnt[i%w]+=v;} ll val=*a[i%w].rbegin()-cnt[i%w]; d[i]=max(d[i],val); } } cout<<*max_element(d.begin(),d.end()); 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...