답안 #113006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113006 2019-05-23T03:54:09 Z jh05013 Pinball (JOI14_pinball) Python 3
51 / 100
1000 ms 6084 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)]
# TODO: compress column numbers

# 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 == 1:
        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 == m:
        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)
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3328 KB Output is correct
2 Correct 24 ms 3436 KB Output is correct
3 Correct 22 ms 3436 KB Output is correct
4 Correct 21 ms 3328 KB Output is correct
5 Correct 23 ms 3428 KB Output is correct
6 Correct 25 ms 3332 KB Output is correct
7 Correct 22 ms 3436 KB Output is correct
8 Correct 22 ms 3356 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3328 KB Output is correct
2 Correct 24 ms 3436 KB Output is correct
3 Correct 22 ms 3436 KB Output is correct
4 Correct 21 ms 3328 KB Output is correct
5 Correct 23 ms 3428 KB Output is correct
6 Correct 25 ms 3332 KB Output is correct
7 Correct 22 ms 3436 KB Output is correct
8 Correct 22 ms 3356 KB Output is correct
9 Correct 31 ms 3336 KB Output is correct
10 Correct 30 ms 3352 KB Output is correct
11 Correct 31 ms 3340 KB Output is correct
12 Correct 30 ms 3340 KB Output is correct
13 Correct 29 ms 3336 KB Output is correct
14 Correct 28 ms 3340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3328 KB Output is correct
2 Correct 24 ms 3436 KB Output is correct
3 Correct 22 ms 3436 KB Output is correct
4 Correct 21 ms 3328 KB Output is correct
5 Correct 23 ms 3428 KB Output is correct
6 Correct 25 ms 3332 KB Output is correct
7 Correct 22 ms 3436 KB Output is correct
8 Correct 22 ms 3356 KB Output is correct
9 Correct 31 ms 3336 KB Output is correct
10 Correct 30 ms 3352 KB Output is correct
11 Correct 31 ms 3340 KB Output is correct
12 Correct 30 ms 3340 KB Output is correct
13 Correct 29 ms 3336 KB Output is correct
14 Correct 28 ms 3340 KB Output is correct
15 Correct 23 ms 3344 KB Output is correct
16 Correct 39 ms 3452 KB Output is correct
17 Correct 208 ms 3760 KB Output is correct
18 Correct 199 ms 3644 KB Output is correct
19 Correct 216 ms 3672 KB Output is correct
20 Correct 207 ms 3736 KB Output is correct
21 Correct 57 ms 3480 KB Output is correct
22 Correct 163 ms 3912 KB Output is correct
23 Correct 171 ms 3696 KB Output is correct
24 Correct 166 ms 3716 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3328 KB Output is correct
2 Correct 24 ms 3436 KB Output is correct
3 Correct 22 ms 3436 KB Output is correct
4 Correct 21 ms 3328 KB Output is correct
5 Correct 23 ms 3428 KB Output is correct
6 Correct 25 ms 3332 KB Output is correct
7 Correct 22 ms 3436 KB Output is correct
8 Correct 22 ms 3356 KB Output is correct
9 Correct 31 ms 3336 KB Output is correct
10 Correct 30 ms 3352 KB Output is correct
11 Correct 31 ms 3340 KB Output is correct
12 Correct 30 ms 3340 KB Output is correct
13 Correct 29 ms 3336 KB Output is correct
14 Correct 28 ms 3340 KB Output is correct
15 Correct 23 ms 3344 KB Output is correct
16 Correct 39 ms 3452 KB Output is correct
17 Correct 208 ms 3760 KB Output is correct
18 Correct 199 ms 3644 KB Output is correct
19 Correct 216 ms 3672 KB Output is correct
20 Correct 207 ms 3736 KB Output is correct
21 Correct 57 ms 3480 KB Output is correct
22 Correct 163 ms 3912 KB Output is correct
23 Correct 171 ms 3696 KB Output is correct
24 Correct 166 ms 3716 KB Output is correct
25 Execution timed out 1058 ms 6084 KB Time limit exceeded
26 Halted 0 ms 0 KB -