Submission #1210681

#TimeUsernameProblemLanguageResultExecution timeMemory
1210681ASGA_RedSeaKnapsack (NOI18_knapsack)C++20
73 / 100
1093 ms672 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); ll s,n;cin>>s>>n; vector<ll>d(s+1,0); while(n--){ ll v,w,k;cin>>v>>w>>k; vector<multiset<ll>>a(w); vector<ll>vv(s+1,0); for(ll i=0;i<=s;i++){ vv[i]=v*((s-i+w)/w); } for(ll 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(ll i=s;i>=w;i--){ a[i%w].erase(a[i%w].find(d[i]+vv[i]));cnt[i%w]+=v; if(i>=w*k)a[i%w].insert(d[i-w*k]+vv[i-w*k]); 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...