oj.uz

답안 #113009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
113009 2019-05-23T04:06:30 Z jh05013 Pinball (JOI14_pinball) Python 3
0 / 100
 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)

Subtask #1
0 / 11.0

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

Subtask #2
0 / 18.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 49.0

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