# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
52491 | 2018-06-26T05:58:12 Z | 0^0(#1358) | Pinball (JOI14_pinball) | C++11 | 1000 ms | 150208 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int m, n; int A[100005], B[100005], C[100005], D[100005]; ll inf = 0x3f3f3f3f3f3f3f3f; map<int,ll> cache1[100005], cache2[100005]; ll dp1(int idx, int p) { if (idx == 0)return A[p] <= 1 ? 0 : inf; if (cache1[idx].count(p))return cache1[idx][p]; ll ret = dp1(idx - 1, p); if (C[idx]>=A[p]&&A[idx]<A[p])ret = min(ret, dp1(idx - 1, idx)+D[idx]); return cache1[idx][p]=ret; } ll dp2(int idx, int p) { if (idx == 0)return B[p] >= n ? 0 : inf; if (cache2[idx].count(p))return cache2[idx][p]; ll ret = dp2(idx - 1, p); if (C[idx]<=B[p]&&B[idx]>B[p])ret = min(ret, dp2(idx - 1, idx)+D[idx]); return cache2[idx][p] = ret; } int main() { scanf("%d%d", &m, &n); for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]); ll ans = inf; for (int i = m; i > 0; i--) { ll now = dp1(i - 1, i) + dp2(i - 1, i) + D[i]; ans = min(ans, now); } printf("%lld\n", ans == inf ? -1 : ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9832 KB | Output is correct |
3 | Correct | 10 ms | 9832 KB | Output is correct |
4 | Correct | 11 ms | 9908 KB | Output is correct |
5 | Correct | 10 ms | 9964 KB | Output is correct |
6 | Correct | 9 ms | 9964 KB | Output is correct |
7 | Correct | 12 ms | 9964 KB | Output is correct |
8 | Correct | 10 ms | 9964 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9832 KB | Output is correct |
3 | Correct | 10 ms | 9832 KB | Output is correct |
4 | Correct | 11 ms | 9908 KB | Output is correct |
5 | Correct | 10 ms | 9964 KB | Output is correct |
6 | Correct | 9 ms | 9964 KB | Output is correct |
7 | Correct | 12 ms | 9964 KB | Output is correct |
8 | Correct | 10 ms | 9964 KB | Output is correct |
9 | Correct | 26 ms | 12496 KB | Output is correct |
10 | Correct | 21 ms | 12496 KB | Output is correct |
11 | Correct | 19 ms | 12496 KB | Output is correct |
12 | Correct | 17 ms | 12520 KB | Output is correct |
13 | Correct | 19 ms | 12520 KB | Output is correct |
14 | Correct | 22 ms | 12520 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9832 KB | Output is correct |
3 | Correct | 10 ms | 9832 KB | Output is correct |
4 | Correct | 11 ms | 9908 KB | Output is correct |
5 | Correct | 10 ms | 9964 KB | Output is correct |
6 | Correct | 9 ms | 9964 KB | Output is correct |
7 | Correct | 12 ms | 9964 KB | Output is correct |
8 | Correct | 10 ms | 9964 KB | Output is correct |
9 | Correct | 26 ms | 12496 KB | Output is correct |
10 | Correct | 21 ms | 12496 KB | Output is correct |
11 | Correct | 19 ms | 12496 KB | Output is correct |
12 | Correct | 17 ms | 12520 KB | Output is correct |
13 | Correct | 19 ms | 12520 KB | Output is correct |
14 | Correct | 22 ms | 12520 KB | Output is correct |
15 | Correct | 12 ms | 12520 KB | Output is correct |
16 | Correct | 36 ms | 15688 KB | Output is correct |
17 | Correct | 392 ms | 72720 KB | Output is correct |
18 | Correct | 404 ms | 72720 KB | Output is correct |
19 | Correct | 408 ms | 72720 KB | Output is correct |
20 | Correct | 450 ms | 72720 KB | Output is correct |
21 | Correct | 77 ms | 72720 KB | Output is correct |
22 | Correct | 316 ms | 72720 KB | Output is correct |
23 | Correct | 344 ms | 72720 KB | Output is correct |
24 | Correct | 300 ms | 72800 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9832 KB | Output is correct |
3 | Correct | 10 ms | 9832 KB | Output is correct |
4 | Correct | 11 ms | 9908 KB | Output is correct |
5 | Correct | 10 ms | 9964 KB | Output is correct |
6 | Correct | 9 ms | 9964 KB | Output is correct |
7 | Correct | 12 ms | 9964 KB | Output is correct |
8 | Correct | 10 ms | 9964 KB | Output is correct |
9 | Correct | 26 ms | 12496 KB | Output is correct |
10 | Correct | 21 ms | 12496 KB | Output is correct |
11 | Correct | 19 ms | 12496 KB | Output is correct |
12 | Correct | 17 ms | 12520 KB | Output is correct |
13 | Correct | 19 ms | 12520 KB | Output is correct |
14 | Correct | 22 ms | 12520 KB | Output is correct |
15 | Correct | 12 ms | 12520 KB | Output is correct |
16 | Correct | 36 ms | 15688 KB | Output is correct |
17 | Correct | 392 ms | 72720 KB | Output is correct |
18 | Correct | 404 ms | 72720 KB | Output is correct |
19 | Correct | 408 ms | 72720 KB | Output is correct |
20 | Correct | 450 ms | 72720 KB | Output is correct |
21 | Correct | 77 ms | 72720 KB | Output is correct |
22 | Correct | 316 ms | 72720 KB | Output is correct |
23 | Correct | 344 ms | 72720 KB | Output is correct |
24 | Correct | 300 ms | 72800 KB | Output is correct |
25 | Execution timed out | 1073 ms | 150208 KB | Time limit exceeded |
26 | Halted | 0 ms | 0 KB | - |