/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// 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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |