結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2020-10-26 09:08:20 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,435 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 17,792 KB |
最終ジャッジ日時 | 2024-07-21 21:15:29 |
合計ジャッジ時間 | 28,646 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 RE * 2 TLE * 10 |
ソースコード
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 = default self.dat = [default] * (self.size * 2) self.f = f def update(self, i, x): i += self.size self.dat[i] = x while i > 0: i >>= 1 self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1]) def query(self, l, r): """半開区間[l,r)""" l += self.size r += self.size lres, rres = self.default, self.default while l < r: if l & 1: lres = self.f(lres, self.dat[l]) l += 1 if r & 1: r -= 1 rres = self.f(self.dat[r], rres) l >>= 1 r >>= 1 res = self.f(lres, rres) return res N, D, K = map(int, input().split()) S = SegmentTree(N) X = [int(input()) for _ in range(N)] for i, x in enumerate(X, 1): S.update(i, x) p_max = 0 lidx = 0 for 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 = profit lidx = i - 1 print(p_max) if p_max: M = X[lidx] + p_max // K ridx = X[lidx:min(lidx + D + 1, N)].index(M) + lidx print(lidx, ridx)