Submission #113006

#	Time	Username	Problem	Language	Result	Execution time	Memory
113006		jh05013	Pinball (JOI14_pinball)	Cpython 3	51 / 100	1058 ms	6084 KiB

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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49