# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
312203 | 2020-10-12T16:23:21 Z | BeanZ | Cloud Computing (CEOI18_clo) | C++14 | 2950 ms | 2296 KB |
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 2e3 + 5; const int lim = 100; ll dp[N][lim + 5]; struct viet{ ll c, f, v; bool operator <(const viet& o) const{ return f > o.f; } }a[N], b[N]; ll c[N], v[N], f[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("A.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n; cin >> n; for (int i = 1; i <= n; i++){ cin >> a[i].c >> a[i].f >> a[i].v; } for (int i = 0; i <= n; i++){ for (int j = 0; j <= lim; j++){ dp[i][j] = -1e18; } } dp[0][0] = 0; sort(a + 1, a + n + 1); ll ans = 0; ll m; cin >> m; for (int i = 1; i <= m; i++){ cin >> b[i].c >> b[i].f >> b[i].v; } sort(b + 1, b + m + 1); /* for (int j = 1; j <= n; j++){ /* for (int k = 0; k <= 50; k++){ if (k >= a[j].c) dp[j][k] = max(dp[j][k], dp[j - 1][k - a[j].c] - a[j].v); //cout << dp[j][k] << " " << j << " " << k << endl; } for (int k = 50; k >= 0; k--){ for (int i = 1; i <= m; i++){ if (k >= a[j].c) dp[j][k] = max(dp[j][k], dp[j - 1][k - a[j].c] - a[j].v); if ((k + c[i]) <= 50 && f[i] <= a[j].f) dp[j][k] = max(dp[j][k], dp[j][k + c[i]] + v[i]); ans = max(ans, dp[j][k]); } } }*/ for (int i = 1; i <= n; i++) dp[i][a[i].c] = -a[i].v; for (int i = 1; i <= m; i++){ //cout << dp[1][0] << endl; for (int j = 1; j <= n; j++){ for (int k = 0; k <= lim; k++){ dp[j][k] = max(dp[j][k], dp[j - 1][k]); if (k >= a[j].c) { dp[j][k] = max(dp[j][k], dp[j - 1][k - a[j].c] - a[j].v); } } for (int k = lim - 1; k >= 0; k--) dp[j][k] = max(dp[j][k], dp[j][k + 1]); } for (int j = n; j >= 1; j--){ //cout << dp[1][1] << endl; for (int k = 0; k <= lim; k++){ //for (int i = 1; i <= m; i++){ //for (int k = 0; k <= 50; k++){ if ((k + b[i].c) <= lim && b[i].f <= a[j].f) dp[j][k] = max(dp[j][k], dp[j][k + b[i].c] + b[i].v); ans = max(ans, dp[j][k]); //cout << dp[j][k] << " " << j << " " << k << endl; //} } } //cout << dp[3][80] << endl; } cout << ans; } /* 3 6 4 3 45 5 3 35 4 1 3 43 3 5 31 4 4 34 3 3 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 21 ms | 384 KB | Output is correct |
6 | Correct | 21 ms | 384 KB | Output is correct |
7 | Correct | 22 ms | 384 KB | Output is correct |
8 | Correct | 23 ms | 500 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 10 ms | 1152 KB | Output is correct |
6 | Correct | 10 ms | 1152 KB | Output is correct |
7 | Correct | 24 ms | 2048 KB | Output is correct |
8 | Correct | 27 ms | 2048 KB | Output is correct |
9 | Correct | 23 ms | 2048 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 6 ms | 384 KB | Output is correct |
4 | Correct | 7 ms | 384 KB | Output is correct |
5 | Correct | 23 ms | 512 KB | Output is correct |
6 | Correct | 23 ms | 512 KB | Output is correct |
7 | Correct | 46 ms | 512 KB | Output is correct |
8 | Correct | 47 ms | 632 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 10 ms | 1664 KB | Output is correct |
4 | Correct | 18 ms | 384 KB | Output is correct |
5 | Correct | 2597 ms | 2296 KB | Output is correct |
6 | Correct | 2921 ms | 2176 KB | Output is correct |
7 | Correct | 2928 ms | 2180 KB | Output is correct |
8 | Correct | 2797 ms | 2168 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 107 ms | 872 KB | Output is correct |
4 | Correct | 695 ms | 1144 KB | Output is correct |
5 | Correct | 2849 ms | 2168 KB | Output is correct |
6 | Correct | 2950 ms | 2152 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 21 ms | 384 KB | Output is correct |
6 | Correct | 21 ms | 384 KB | Output is correct |
7 | Correct | 22 ms | 384 KB | Output is correct |
8 | Correct | 23 ms | 500 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 0 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 10 ms | 1152 KB | Output is correct |
14 | Correct | 10 ms | 1152 KB | Output is correct |
15 | Correct | 24 ms | 2048 KB | Output is correct |
16 | Correct | 27 ms | 2048 KB | Output is correct |
17 | Correct | 23 ms | 2048 KB | Output is correct |
18 | Correct | 1 ms | 384 KB | Output is correct |
19 | Correct | 1 ms | 384 KB | Output is correct |
20 | Correct | 6 ms | 384 KB | Output is correct |
21 | Correct | 7 ms | 384 KB | Output is correct |
22 | Correct | 23 ms | 512 KB | Output is correct |
23 | Correct | 23 ms | 512 KB | Output is correct |
24 | Correct | 46 ms | 512 KB | Output is correct |
25 | Correct | 47 ms | 632 KB | Output is correct |
26 | Correct | 1 ms | 384 KB | Output is correct |
27 | Correct | 1 ms | 384 KB | Output is correct |
28 | Correct | 10 ms | 1664 KB | Output is correct |
29 | Correct | 18 ms | 384 KB | Output is correct |
30 | Correct | 2597 ms | 2296 KB | Output is correct |
31 | Correct | 2921 ms | 2176 KB | Output is correct |
32 | Correct | 2928 ms | 2180 KB | Output is correct |
33 | Correct | 2797 ms | 2168 KB | Output is correct |
34 | Correct | 0 ms | 384 KB | Output is correct |
35 | Correct | 5 ms | 384 KB | Output is correct |
36 | Correct | 107 ms | 872 KB | Output is correct |
37 | Correct | 695 ms | 1144 KB | Output is correct |
38 | Correct | 2849 ms | 2168 KB | Output is correct |
39 | Correct | 2950 ms | 2152 KB | Output is correct |
40 | Correct | 192 ms | 760 KB | Output is correct |
41 | Correct | 631 ms | 1024 KB | Output is correct |
42 | Correct | 1651 ms | 1784 KB | Output is correct |
43 | Correct | 2915 ms | 2176 KB | Output is correct |
44 | Correct | 2897 ms | 2188 KB | Output is correct |
45 | Correct | 2893 ms | 2220 KB | Output is correct |
46 | Correct | 721 ms | 1280 KB | Output is correct |
47 | Correct | 1644 ms | 1744 KB | Output is correct |
48 | Correct | 1574 ms | 1784 KB | Output is correct |