답안 #113006

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113006	2019-05-23T03:54:09 Z	jh05013	Pinball (JOI14_pinball)	Python 3	51 / 100	1000 ms	6084 KB

pinball

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)

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	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

Subtask #2

18.0 / 18.0

#	결과	실행 시간	메모리	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

Subtask #3

22.0 / 22.0

#	결과	실행 시간	메모리	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

Subtask #4

0 / 49.0

#	결과	실행 시간	메모리	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	-