PythonでJOI難易度5を埋める #17

D - 暑い日々 (Hot days) 非常に眠いので，支離滅裂なことを書いています．いつもだろ

考えたこと
日目の選択に日目以外の情報は必要ない．なので，DPする．DP[i][j]は日目に個目の服を選んだときの値を保持している．

d, n = map(int, input().split())
t = [int(input()) for _ in range(d)]
abc = [list(map(int, input().split())) for _ in range(n)]

dp = [[-1] * n for _ in range(d)]
for i in range(n):
    if abc[i][0] <= t[0] <= abc[i][1]:
        dp[0][i] = abc[i][2]

ans = 0
for i in range(1, d):
    tmp = t[i]
    for k in range(n):
        if abc[k][0] <= tmp <= abc[k][1]:
            for j in range(n):
                if dp[i - 1][j] == -1:
                    continue
                if i == 1:
                    dp[i][k] = max(abs(abc[k][2] - abc[j][2]), dp[i][k])
                    continue
                dp[i][k] = max(dp[i-1][j] + abs(abc[k][2] - abc[j][2]), dp[i][k])

print(max(dp[-1]))