#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fwd(i, a, n) for (int i = (a); i < (n); i ++)
#define rep(i, n) fwd(i, 0, n)
#define all(X) begin(X), end(X)
#define sz(X) ((int)X.size())
#define st first
#define nd second
#define vi vector<int>
#define pii pair<int, int>
#define ll long long
#define vll vector<long long>
#ifdef LOC
auto &operator<<(auto &out, pair<auto, auto> a) {
return out << "(" << a.st << ", " << a.nd << ")";
}
auto &operator<<(auto &out, auto a) {
out << "{";
for (auto b : a)
out << b << ", ";
return out << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << '\n'; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) 0
#endif
const int maxN = 2000 + 10;
const int maxC = 100;
const ll inf = 1e18;
struct computer {
int c, f, v;
computer() {}
computer(int c, int f, int v) : c(c), f(f), v(v) {}
};
struct order {
int c, f, v;
order() {}
order(int c, int f, int v) : c(c), f(f), v(v) {}
};
computer comp[maxN];
order ord[maxN];
ll dp[maxN][maxC + 1];
void ext(int cid, int m) {
rep(i, m + 1)
for (int j = maxC; j >= 0; j --) {
int s = min(maxC, j + comp[cid].c);
ll t = dp[i][j] - comp[cid].v;
if (t > dp[i][s]) dp[i][s] = t;
}
rep(i, m) {
rep(j, maxC + 1)
if (dp[i][j] > dp[i + 1][j]) dp[i + 1][j] = dp[i][j];
if (ord[i + 1].f > comp[cid].f) continue;
rep(j, maxC + 1 - ord[i + 1].c) {
ll t = dp[i][j + ord[i + 1].c] + ord[i + 1].v;
if (t > dp[i + 1][j]) dp[i + 1][j] = t;
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i ++) {
int c, f, v;
cin >> c >> f >> v;
comp[i] = computer(c, f, v);
}
int m;
cin >> m;
for (int i = 1; i <= m; i ++) {
int c, f, v;
cin >> c >> f >> v;
ord[i] = order(c, f, v);
}
sort(comp + 1, comp + n + 1, [&](auto &a, auto &b) {
return a.f > b.f;
});
sort(ord + 1, ord + m + 1, [&](auto &a, auto &b) {
return a.f > b.f;
});
rep(i, m + 1)
fill(dp[i], dp[i] + maxC + 1, -inf);
dp[0][0] = 0;
for (int i = 1; i <= n; i ++) {
ext(i, m);
}
cout << *max_element(dp[m], dp[m] + maxC + 1) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
7 ms |
1884 KB |
Output is correct |
6 |
Correct |
7 ms |
1884 KB |
Output is correct |
7 |
Correct |
6 ms |
2120 KB |
Output is correct |
8 |
Correct |
7 ms |
2116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
4 ms |
348 KB |
Output is correct |
6 |
Correct |
3 ms |
348 KB |
Output is correct |
7 |
Correct |
7 ms |
548 KB |
Output is correct |
8 |
Correct |
9 ms |
348 KB |
Output is correct |
9 |
Correct |
7 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
2 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
8 ms |
348 KB |
Output is correct |
6 |
Correct |
7 ms |
348 KB |
Output is correct |
7 |
Correct |
11 ms |
604 KB |
Output is correct |
8 |
Correct |
11 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
464 KB |
Output is correct |
3 |
Correct |
3 ms |
348 KB |
Output is correct |
4 |
Correct |
6 ms |
1884 KB |
Output is correct |
5 |
Correct |
733 ms |
1884 KB |
Output is correct |
6 |
Correct |
808 ms |
2136 KB |
Output is correct |
7 |
Correct |
863 ms |
2140 KB |
Output is correct |
8 |
Correct |
818 ms |
2128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
25 ms |
684 KB |
Output is correct |
4 |
Correct |
218 ms |
1616 KB |
Output is correct |
5 |
Correct |
705 ms |
2140 KB |
Output is correct |
6 |
Correct |
768 ms |
2128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
7 ms |
1884 KB |
Output is correct |
6 |
Correct |
7 ms |
1884 KB |
Output is correct |
7 |
Correct |
6 ms |
2120 KB |
Output is correct |
8 |
Correct |
7 ms |
2116 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
348 KB |
Output is correct |
13 |
Correct |
4 ms |
348 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
7 ms |
548 KB |
Output is correct |
16 |
Correct |
9 ms |
348 KB |
Output is correct |
17 |
Correct |
7 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
2 ms |
348 KB |
Output is correct |
21 |
Correct |
1 ms |
348 KB |
Output is correct |
22 |
Correct |
8 ms |
348 KB |
Output is correct |
23 |
Correct |
7 ms |
348 KB |
Output is correct |
24 |
Correct |
11 ms |
604 KB |
Output is correct |
25 |
Correct |
11 ms |
604 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
0 ms |
464 KB |
Output is correct |
28 |
Correct |
3 ms |
348 KB |
Output is correct |
29 |
Correct |
6 ms |
1884 KB |
Output is correct |
30 |
Correct |
733 ms |
1884 KB |
Output is correct |
31 |
Correct |
808 ms |
2136 KB |
Output is correct |
32 |
Correct |
863 ms |
2140 KB |
Output is correct |
33 |
Correct |
818 ms |
2128 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
25 ms |
684 KB |
Output is correct |
37 |
Correct |
218 ms |
1616 KB |
Output is correct |
38 |
Correct |
705 ms |
2140 KB |
Output is correct |
39 |
Correct |
768 ms |
2128 KB |
Output is correct |
40 |
Correct |
48 ms |
888 KB |
Output is correct |
41 |
Correct |
156 ms |
1372 KB |
Output is correct |
42 |
Correct |
438 ms |
1704 KB |
Output is correct |
43 |
Correct |
711 ms |
2140 KB |
Output is correct |
44 |
Correct |
685 ms |
2148 KB |
Output is correct |
45 |
Correct |
660 ms |
2160 KB |
Output is correct |
46 |
Correct |
198 ms |
1284 KB |
Output is correct |
47 |
Correct |
408 ms |
1716 KB |
Output is correct |
48 |
Correct |
385 ms |
1624 KB |
Output is correct |