結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2019-08-09 18:59:53 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,433 bytes |
コンパイル時間 | 369 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 103,936 KB |
最終ジャッジ日時 | 2024-12-11 14:26:43 |
合計ジャッジ時間 | 17,318 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 TLE * 1 |
ソースコード
from collections import defaultdictclass SegmentTree:def __init__(self, N):n_ = 1while n_ < N:n_ *= 2self.n = n_self.arr = [-10 ** 18] * (2*self.n - 1)def update(self, k, a):k += self.n - 1self.arr[k] = awhile k > 0:k = (k - 1) // 2self.arr[k] = max(self.arr[2*k + 1], self.arr[2*k + 2])def query_sub(self, a, b, k, l, r):if r <= a or b <= l:return -10 ** 18if a <= l and r <= b:return self.arr[k]else:vl = self.query_sub(a, b, 2*k + 1, l, (l+r) / 2)vr = self.query_sub(a, b, 2*k + 2, (l+r) / 2, r)return max(vl, vr)def query(self, a, b):return self.query_sub(a, b, 0, 0, self.n)N, D, K = map(int, input().split())x = [int(input()) for _ in range(N)]seg_tree = SegmentTree(N)for i in range(N):seg_tree.update(i, x[i])dic = defaultdict(list)for i in range(N):dic[x[i]].append(i)ans1 = -10 ** 18for i in range(N):m = seg_tree.query(i, min(i+D+1, N))if (m-x[i]) * K > ans1:ans1 = (m - x[i]) * Kans2 = il = dic[m]for l_i in sorted(l):if i <= l_i < min(i+D+1, N):ans3 = l_ibreakif ans1 == 0:print(0)else:print(ans1)print(ans2, ans3)