| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 113009 |
2019-05-23T04:06:30 Z |
jh05013 |
Pinball (JOI14_pinball) |
Python 3 |
|
24 ms |
3436 KB |
input = __import__('sys').stdin.readline
MIS = lambda: map(int,input().split())
INF = 10**18
n, m = MIS()
plat = [tuple(MIS()) for i in range(n)]
C = set()
for l, r, c, cost in plat: C|= {l,r,c}
C = dict(zip(sorted(C), range(len(C))))
plat = [(C[l], C[r], C[c], cost) for l, r, c, cost in plat]
# dpl[i] = "min cost where ball starting from #1 falls to i-th platform"
# TODO: change to RMQ
dpl = []
for i in range(n):
l, r, c, cost = plat[i]
if l == 0:
dpl.append(cost)
continue
dpl.append(cost + min((dpl[j] for j in range(i) if l<=plat[j][2]<=r), default = INF))
# dpu[i] = "min cost where ball starting from #m falls to i-th platform"
dpr = []
for i in range(n):
l, r, c, cost = plat[i]
if r == len(C)-1:
dpr.append(cost)
continue
dpr.append(cost + min((dpr[j] for j in range(i) if l<=plat[j][2]<=r), default = INF))
ans = min(dpl[i]+dpr[i]-plat[i][3] for i in range(n))
print(ans if ans < INF else -1)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
21 ms |
3436 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3436 KB |
Output is correct |
| 5 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 6 |
Correct |
22 ms |
3428 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
3428 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
21 ms |
3436 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3436 KB |
Output is correct |
| 5 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 6 |
Correct |
22 ms |
3428 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
3428 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
21 ms |
3436 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3436 KB |
Output is correct |
| 5 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 6 |
Correct |
22 ms |
3428 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
3428 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
3420 KB |
Output is correct |
| 2 |
Correct |
21 ms |
3436 KB |
Output is correct |
| 3 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 4 |
Correct |
24 ms |
3436 KB |
Output is correct |
| 5 |
Correct |
22 ms |
3436 KB |
Output is correct |
| 6 |
Correct |
22 ms |
3428 KB |
Output is correct |
| 7 |
Incorrect |
23 ms |
3428 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
