結果
問題 | No.844 split game |
ユーザー |
![]() |
提出日時 | 2019-06-28 21:38:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 326 ms / 2,000 ms |
コード長 | 1,552 bytes |
コンパイル時間 | 429 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 101,864 KB |
最終ジャッジ日時 | 2024-07-02 04:29:49 |
合計ジャッジ時間 | 10,966 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 56 |
ソースコード
from operator import itemgetter import sys class Segtree: def __init__(self, A, intv, initialize = True, segf = min): self.N = len(A) self.N0 = 2**(self.N-1).bit_length() self.intv = intv self.segf = segf if initialize: self.data = [intv]*(self.N0-1) + A + [intv]*(self.N0 - self.N + 1) for i in range(self.N0-2, -1, -1): self.data[i] = self.segf(self.data[2*i+1], self.data[2*i+2]) else: self.data = [intv]*(2*self.N0) def update(self, k, x): k += self.N0-1 self.data[k] = x while k >= 0 : k = (k-1)//2 self.data[k] = self.segf(self.data[2*k+1], self.data[2*k+2]) def query(self, l, r): L, R = l+self.N0, r+self.N0 s = self.intv while L < R: if R & 1: R -= 1 s = self.segf(s, self.data[R-1]) if L & 1: s = self.segf(s, self.data[L-1]) L += 1 L >>= 1 R >>= 1 return s N, M, A = map(int, input().split()) LRP = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)] Edge = [[] for _ in range(N+1)] for l, r, p in LRP: Edge[r].append((l, p)) Dp = [0]*(N+1) dp = Segtree([0]*(N+1), 0, False, max) for i in range(1, N+1): res = -A res = max(dp.query(0, i) - A, res) for l, c in Edge[i]: res = max(res, Dp[l-1] + c - A) Dp[i] = res dp.update(i, res) Dp[-1] += A print(max(Dp))