/**
00 00 11 00 00 111111 00000 111111 000000
00 00 1111 0000 11 00 11 11 000000
0000 11 11 00 11 00000 111111 00
00 00 11111111 0000 11 00 11 11 00
00 00 11 11 00 00 111111 00000 11 11 00
**/
#include<bits/stdc++.h>
using namespace std;
void setIO(string s) {
freopen((s+".inp").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
void setIOusaco(string s) {
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define fast ios::sync_with_stdio(false); cin.tie(0)
template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}
void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifdef TAP
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...)
#endif
int main() {
fast;
int s, n;
cin >> s >> n;
vt<vt<pair<ll, ll> > > m(s+1);
vt<vt<ll> > temp(s+1);
fto(i, 1, n) {
int v, w, k;
cin >> v >> w >> k;
m[w].eb(mp(v, k));
}
vt<int> sth;
fto(i, 1, s) {
if (m[i].empty()) continue;
sth.pb(i);
sort(all(m[i]), [](pair<ll, ll> a, pair<ll, ll> b)->bool {
return a.ff < b.ff;
});
int need = s/i;
while(!m[i].empty() && need > 0) {
temp[i].pb(m[i][sz(m[i])-1].ff);
if (sz(temp[i]) > 1) temp[i][sz(temp[i])-1] += temp[i][sz(temp[i])-2];
if ((m[i][sz(m[i])-1].ss -= 1) == 0) {
m[i].pop_back();
}
--need;
}
}
vt<vt<ll> > f(2, vt<ll>(s+2, 0));
fto(i, 0, sz(sth)-1) {
int li = i&1;
int w = sth[i];
fto(j, 1, s) f[li][j] = f[li^1][j];
//bug(w);
//bug(temp[w]);
fto(j, 0, sz(temp[w])-1) {
fto(k, w*(j+1), s) {
f[li][k] = max(f[li][k], f[li^1][k-w*(j+1)] + temp[w][j]);
}
}
//bug(f[li]);
}
ll ans = 0;
fto(i, 1, s) {
ans = max(ans, f[(sz(sth)-1)&1][i]);
}
cout << ans << '\n';
return 0;
}
Compilation message
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen((s+".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setIOusaco(std::string)':
knapsack.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
460 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
3 ms |
460 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
1 ms |
460 KB |
Output is correct |
19 |
Correct |
2 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
3 ms |
460 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
22 |
Correct |
1 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
0 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
456 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
3 ms |
460 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
460 KB |
Output is correct |
22 |
Correct |
1 ms |
460 KB |
Output is correct |
23 |
Correct |
2 ms |
460 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
204 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
0 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
460 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
456 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
35 |
Correct |
30 ms |
2460 KB |
Output is correct |
36 |
Correct |
32 ms |
2496 KB |
Output is correct |
37 |
Correct |
30 ms |
3456 KB |
Output is correct |
38 |
Correct |
35 ms |
3748 KB |
Output is correct |
39 |
Correct |
42 ms |
4344 KB |
Output is correct |
40 |
Correct |
60 ms |
4784 KB |
Output is correct |
41 |
Correct |
41 ms |
4036 KB |
Output is correct |
42 |
Correct |
40 ms |
4048 KB |
Output is correct |
43 |
Correct |
46 ms |
4048 KB |
Output is correct |
44 |
Correct |
51 ms |
4148 KB |
Output is correct |
45 |
Correct |
38 ms |
4808 KB |
Output is correct |
46 |
Correct |
29 ms |
4000 KB |
Output is correct |
47 |
Correct |
39 ms |
5004 KB |
Output is correct |
48 |
Correct |
44 ms |
4684 KB |
Output is correct |
49 |
Correct |
28 ms |
4516 KB |
Output is correct |
50 |
Correct |
47 ms |
4248 KB |
Output is correct |