結果

問題 No.844 split game
コンテスト
ユーザー neterukun
提出日時 2019-06-28 22:16:54
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 704 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 91,716 KB
最終ジャッジ日時 2024-07-02 04:51:26
合計ジャッジ時間 9,779 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from operator import itemgetter


input = sys.stdin.readline
n, m, a = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]

info = sorted(info, key = itemgetter(1)) + [[-1, -1, -1]]

dp = [0]*(n+1)
cnt = 1
max_dp = 0
for i in range(m):
    if cnt != info[i][1]:
        for j in range(cnt, info[i][1]):
            dp[j] = max_dp - a
        cnt = info[i][1]
    if info[i][1] == n:
        dp[info[i][1]] = max(dp[info[i][1]], dp[info[i][0] - 1] + info[i][2])
    else:
        dp[info[i][1]] = max(dp[info[i][1]], dp[info[i][0] - 1] + info[i][2] - a)
    if info[i][1] != info[i+1][1]:
        cnt += 1
    max_dp = max(max_dp, dp[info[i][1]])
print(max(dp))
0