# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
139419 | 2019-07-31T16:22:45 Z | luciocf | Cloud Computing (CEOI18_clo) | C++14 | 1816 ms | 3704 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e3+10; const int maxc = 51; const ll inf = 2e18+10; struct Obj { int c, f, v; } a[maxn], b[maxn]; int n, m; ll dp[2][maxn][2*maxc]; void upd(ll &a, ll b) { a = max(a, b); } bool comp(Obj a, Obj b) { return a.f > b.f; } int main(void) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d %d %d", &a[i].c, &a[i].f, &a[i].v); scanf("%d", &m); for (int i = 1; i <= m; i++) scanf("%d %d %d", &b[i].c, &b[i].f, &b[i].v); sort(a+1, a+n+1, comp); sort(b+1, b+m+1, comp); for (int i = n; i >= 0; i--) { int at = i%2, pre = (i+1)%2; for (int j = m; j >= 1; j--) { for (int c = 2*maxc-1; c >= 0; c--) { if (a[i+1].f < b[j].f && c > 0 && c < b[j].c) { upd(dp[at][j][c], dp[at][j+1][c]); continue; } upd(dp[at][j][c], dp[pre][j][c]); upd(dp[at][j][c], dp[at][j+1][c]); if (c >= b[j].c) upd(dp[at][j][c], 1ll*b[j].v + dp[at][j+1][c-b[j].c]); if (i < n && c < maxc && a[i+1].f >= b[j].f) upd(dp[at][j][c], dp[pre][j][c+a[i+1].c] - 1ll*a[i+1].v); } } } printf("%lld\n", max(0ll, dp[0][1][0])); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 504 KB | Output is correct |
4 | Correct | 3 ms | 632 KB | Output is correct |
5 | Correct | 19 ms | 3448 KB | Output is correct |
6 | Correct | 22 ms | 3448 KB | Output is correct |
7 | Correct | 21 ms | 3576 KB | Output is correct |
8 | Correct | 20 ms | 3576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 8 ms | 376 KB | Output is correct |
6 | Correct | 8 ms | 376 KB | Output is correct |
7 | Correct | 14 ms | 376 KB | Output is correct |
8 | Correct | 17 ms | 376 KB | Output is correct |
9 | Correct | 16 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 6 ms | 504 KB | Output is correct |
4 | Correct | 6 ms | 504 KB | Output is correct |
5 | Correct | 18 ms | 504 KB | Output is correct |
6 | Correct | 17 ms | 504 KB | Output is correct |
7 | Correct | 30 ms | 760 KB | Output is correct |
8 | Correct | 30 ms | 792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 7 ms | 376 KB | Output is correct |
4 | Correct | 18 ms | 3324 KB | Output is correct |
5 | Correct | 1651 ms | 3420 KB | Output is correct |
6 | Correct | 1796 ms | 3656 KB | Output is correct |
7 | Correct | 1816 ms | 3680 KB | Output is correct |
8 | Correct | 1742 ms | 3704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 504 KB | Output is correct |
3 | Correct | 63 ms | 888 KB | Output is correct |
4 | Correct | 466 ms | 2296 KB | Output is correct |
5 | Correct | 1523 ms | 3704 KB | Output is correct |
6 | Correct | 1791 ms | 3704 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 376 KB | Output is correct |
3 | Correct | 3 ms | 504 KB | Output is correct |
4 | Correct | 3 ms | 632 KB | Output is correct |
5 | Correct | 19 ms | 3448 KB | Output is correct |
6 | Correct | 22 ms | 3448 KB | Output is correct |
7 | Correct | 21 ms | 3576 KB | Output is correct |
8 | Correct | 20 ms | 3576 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 376 KB | Output is correct |
12 | Correct | 3 ms | 376 KB | Output is correct |
13 | Correct | 8 ms | 376 KB | Output is correct |
14 | Correct | 8 ms | 376 KB | Output is correct |
15 | Correct | 14 ms | 376 KB | Output is correct |
16 | Correct | 17 ms | 376 KB | Output is correct |
17 | Correct | 16 ms | 376 KB | Output is correct |
18 | Correct | 0 ms | 376 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 6 ms | 504 KB | Output is correct |
21 | Correct | 6 ms | 504 KB | Output is correct |
22 | Correct | 18 ms | 504 KB | Output is correct |
23 | Correct | 17 ms | 504 KB | Output is correct |
24 | Correct | 30 ms | 760 KB | Output is correct |
25 | Correct | 30 ms | 792 KB | Output is correct |
26 | Correct | 2 ms | 376 KB | Output is correct |
27 | Correct | 2 ms | 376 KB | Output is correct |
28 | Correct | 7 ms | 376 KB | Output is correct |
29 | Correct | 18 ms | 3324 KB | Output is correct |
30 | Correct | 1651 ms | 3420 KB | Output is correct |
31 | Correct | 1796 ms | 3656 KB | Output is correct |
32 | Correct | 1816 ms | 3680 KB | Output is correct |
33 | Correct | 1742 ms | 3704 KB | Output is correct |
34 | Correct | 3 ms | 376 KB | Output is correct |
35 | Correct | 4 ms | 504 KB | Output is correct |
36 | Correct | 63 ms | 888 KB | Output is correct |
37 | Correct | 466 ms | 2296 KB | Output is correct |
38 | Correct | 1523 ms | 3704 KB | Output is correct |
39 | Correct | 1791 ms | 3704 KB | Output is correct |
40 | Correct | 103 ms | 1272 KB | Output is correct |
41 | Correct | 348 ms | 2296 KB | Output is correct |
42 | Correct | 998 ms | 2936 KB | Output is correct |
43 | Correct | 1759 ms | 3576 KB | Output is correct |
44 | Correct | 1801 ms | 3704 KB | Output is correct |
45 | Correct | 1480 ms | 3704 KB | Output is correct |
46 | Correct | 436 ms | 2044 KB | Output is correct |
47 | Correct | 973 ms | 2848 KB | Output is correct |
48 | Correct | 933 ms | 2808 KB | Output is correct |