#include <bits/stdc++.h>
#define int long long
#define f first
#define s second
using namespace std;
vector<pair<int, int>> a[2001];
int dp[2001][2001];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, s;
cin >> s >> n;
for (int i = 1;i<=n;++i){
int v, w, k;
cin >> v >> w >> k;
a[w].push_back({v, k});
}
for (int i = 1;i<=s;++i){
sort(a[i].begin(),a[i].end(), [](pair<int, int>p, pair<int, int> q){
return p.f > q.f;
});
}
for (int i = 1;i<=s;++i){
for (int j = 1;j<=s;++j){
dp[i][j] = max(dp[i][j], dp[i][j-1]);
int tmp = i-j;
int dem = 1;
int tro = -1;
int pf = 0;
int pre = 0;
while(tmp >= 0 and tro < (int)a[j].size()){
// cout << tmp << ' ' << tro << '\n';
// cout << "NGU\n";
if(dem>pf){
tro++;
if(tro==a[j].size())break;
pf+=a[j][tro].s;
}
pre += a[j][tro].f;
dp[i][j] = max(dp[i][j], dp[tmp][j-1] + pre);
tmp-=j;
dem++;
}
}
}
/*for (int i = 1;i<=s;++i){
for (int j = 1;j<=s;++j){
cout << dp[i][j] << ' ';
}
cout << '\n';
}*/
cout << dp[s][s];
}
# | 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... |