結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2020-10-26 09:14:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 239 ms / 1,000 ms |
コード長 | 1,438 bytes |
コンパイル時間 | 398 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 82,176 KB |
最終ジャッジ日時 | 2024-07-21 21:16:12 |
合計ジャッジ時間 | 6,229 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
class SegmentTree:"""https://qiita.com/dn6049949/items/afa12d5d079f518de368 から拝借しています。"""def __init__(self, size, f=lambda x, y: max(x, y), default=0):self.size = 2 ** (size - 1).bit_length()self.default = defaultself.dat = [default] * (self.size * 2)self.f = fdef update(self, i, x):i += self.sizeself.dat[i] = xwhile i > 0:i >>= 1self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])def query(self, l, r):"""半開区間[l,r)"""l += self.sizer += self.sizelres, rres = self.default, self.defaultwhile l < r:if l & 1:lres = self.f(lres, self.dat[l])l += 1if r & 1:r -= 1rres = self.f(self.dat[r], rres)l >>= 1r >>= 1res = self.f(lres, rres)return resN, D, K = map(int, input().split())S = SegmentTree(N + 1)X = [int(input()) for _ in range(N)]for i, x in enumerate(X, 1):S.update(i, x)p_max = 0lidx = 0for i, x in enumerate(X, 1):M = S.query(i, min(i + D, N) + 1)profit = K * (M - x)if p_max < profit:p_max = profitlidx = i - 1print(p_max)if p_max:M = X[lidx] + p_max // Kridx = X[lidx:min(lidx + D + 1, N)].index(M) + lidxprint(lidx, ridx)