// author : _anhtun.hi_
#include <bits/stdc++.h>
#define ll long long
#define ii pair<ll, ll>
#define fi first
#define se second
#define c_bit(i) __builtin_popcountll(i)
#define Bit(mask, i) ((mask >> i) & 1)
#define onbit(mask, i) ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))
#define all(data) data.begin(), data.end()
#define reset(h, v) memset(h, v, sizeof h)
#define Forv(i, a) for(auto& i : a)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
using namespace std;
void maximize(auto &a, auto b) {a = max(a, b);}
void minimize(auto &a, auto b) {a = min(a, b);}
//#define int long long
const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0};
const int MAXN = 2e3 + 10, LOG = 20, base = 311;
const ll mod = 1e9 + 7;
const ll oo = 1e18;
int n, s;
vector<ii> List[MAXN];
vector<vector<ll>> dp[MAXN];
ll a[MAXN][MAXN];
int idx[MAXN];
ll solve(int i, int S, int j){
if (S < 0) return -oo;
if (i > s) return (S == 0) ? 0 : -oo;
if (~dp[i][S][j]) return dp[i][S][j];
ll res = 0;
maximize(res, solve(i + 1, S, 0));
if (a[i][j + 1] != 0)
maximize(res, solve(i, S - i, j + 1) + a[i][j + 1]);
return dp[i][S][j] = res;
}
void Solve(){
cin >> s >> n;
For(i, 1, n){
int v, w, k;
cin >> v >> w >> k;
List[w].push_back({v, k});
}
For(w, 1, s){
sort(all(List[w]), [&](ii a, ii b){
return (a.fi > b.fi) || (a.fi == b.fi && a.se > b.se);
});
if (List[w].size()) {
int id = 0;
// cerr << w << '\n';
for(auto [v, k] : List[w]){
// cerr << v << ' ' << k << '\n';
For(j, 1, k) {
a[w][++id] = v;
if (id > s / w + 10) break;
}
if (id > s / w + 10) break;
}
idx[w] = id;
// For(j, 1, id) cerr << a[w][j] << ' '; cerr << '\n';
}
dp[w].assign(s + 2, vector<ll>(s / w + 20, -1));
}
cout << solve(1, s, 0) << '\n';
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
if (fopen("NOI18_knapsack.inp", "r")){
freopen("NOI18_knapsack.inp", "r", stdin);
freopen("NOI18_knapsack.out", "w", stdout);
}
int tc = 1; // cin >> tc;
while (tc --) Solve();
return 0;
}
Compilation message
knapsack.cpp:18:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | void maximize(auto &a, auto b) {a = max(a, b);}
| ^~~~
knapsack.cpp:18:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
18 | void maximize(auto &a, auto b) {a = max(a, b);}
| ^~~~
knapsack.cpp:19:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | void minimize(auto &a, auto b) {a = min(a, b);}
| ^~~~
knapsack.cpp:19:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | void minimize(auto &a, auto b) {a = min(a, b);}
| ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | freopen("NOI18_knapsack.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen("NOI18_knapsack.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
192 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
193 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
193 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
192 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
192 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
