結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2020-12-24 16:21:12 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 772 ms / 1,000 ms |
コード長 | 2,213 bytes |
コンパイル時間 | 2,282 ms |
コンパイル使用メモリ | 79,904 KB |
実行使用メモリ | 57,848 KB |
最終ジャッジ日時 | 2024-09-21 16:57:38 |
合計ジャッジ時間 | 20,412 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import java.util.*;public class Main {public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int d = sc.nextInt();long k = sc.nextInt();int[] arr = new int[n];SegmentTree st = new SegmentTree(n);for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();st.update(i, arr[i]);}long max = 0;int start = 0;int end = 0;for (int i = 1; i < n; i++) {long tmp = st.query(Math.max(i - d, 0), i);if (max < arr[i] - tmp) {max = arr[i] - tmp;end = i;for (int j = Math.max(i - d, 0); j < i; j++) {if (arr[j] == tmp) {start = j;break;}}}max = Math.max(max, arr[i] - tmp);}System.out.println(max * k);if (max > 0) {System.out.println(start + " " + end);}}}class SegmentTree {static final int INF = Integer.MAX_VALUE;int size;int base;int[] tree;public SegmentTree(int size) {this.size = size;base = 1;while (base < size) {base <<= 1;}tree = new int[base * 2 - 1];Arrays.fill(tree, Integer.MAX_VALUE);}public void update(int idx, int value) {updateTree(idx + base - 1, value);}private void updateTree(int idx, int value) {tree[idx] = value;if (idx == 0) {return;}if (idx % 2 == 1) {updateTree((idx - 1) / 2, Math.min(value, tree[idx + 1]));} else {updateTree((idx - 1) / 2, Math.min(value, tree[idx - 1]));}}public int query(int min, int max) {return query(min, max, 0, 0, base);}public int query(int min, int max, int idx, int left, int right) {if (min >= right || max < left) {return INF;}if (min <= left && right - 1 <= max) {return tree[idx];}int x1 = query(min, max, 2 * idx + 1, left, (left + right) / 2);int x2 = query(min, max, 2 * idx + 2, (left + right) / 2, right);return Math.min(x1, x2);}}