結果
問題 | No.844 split game |
ユーザー |
|
提出日時 | 2024-10-10 14:15:29 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 609 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 82,440 KB |
実行使用メモリ | 88,888 KB |
最終ジャッジ日時 | 2024-10-10 14:15:39 |
合計ジャッジ時間 | 8,706 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 WA * 31 |
ソースコード
N,M,a = map(int,input().split())D = [[] for _ in range(N+1)]for _ in range(M):l,r,p = map(int,input().split())D[r].append((l,p))dp = [0]*(N+1)for i in range(1,N+1):dp[i] = dp[i-1]if len(D[i])>0:for l,p in D[i]:dp[i] = max(dp[i],dp[l-1]+p)L = [0]*(N+1)d = dp[N]for i in range(N,0,-1):if d==dp[i]>dp[i-1]:r = ifor l0,p0 in D[i]:if dp[i]==dp[l0-1]+p0:l = l0p = p0breakd -= pL[r] = 1L[l-1] = 1L[0] = 0L[N] = 0ans = max(0,dp[N]-sum(L)*a)print(ans)