#include<bits/stdc++.h>
using namespace std;
int dp[2001][2001];
unordered_map<int,vector<pair<int,int>>> m;
long long func(int i,int s){
if(i==2001) return 0;
if(dp[i][s]!=-1)return dp[i][s];
long long ans=0;
long long val=0;
int chk=0;
ans=func(i+1,s);
int cnt=1;
for(auto p:m[i]){
for(int j=1;j<=p.second;j++){
if(cnt*i<=s){
val+=p.first;
ans=max(ans,val+func(i+1,s-cnt*i));
cnt++;
}
else {
chk=1;
break;
}
}
if(chk) break;
}
return dp[i][s]=ans;
}
int main(){
int s,n;
cin>>s>>n;
for(int i=0;i<=2000;i++){
for(int j=0;j<=2000;j++){
dp[i][j]=-1;
}
}
for(int i=0;i<n;i++){
int v,w,k;
cin>>v>>w>>k;
m[w].push_back({v,k});
}
for(int i=1;i<=2000;i++){{
sort(m[i].rbegin(),m[i].rend());
}}
cout<<func(1,s)<<endl;;
}
# | 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... |