結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2019-07-06 15:16:39 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 883 ms / 1,000 ms |
コード長 | 1,948 bytes |
コンパイル時間 | 3,947 ms |
コンパイル使用メモリ | 79,320 KB |
実行使用メモリ | 72,284 KB |
最終ジャッジ日時 | 2024-07-20 00:18:35 |
合計ジャッジ時間 | 22,803 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
import java.util.*;public class Main {static int N;static long[][] dat;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();init(n);int d = sc.nextInt();long k = sc.nextLong();long[] a = new long[n];for(int i = 0; i < n; i++) {a[i] = sc.nextLong();update(i, a[i]);}long ans = 0;int p = 0;long m1 = 0;long m2 = 0;for(int i = 0; i < n - 1; i++) {long[] t = query(i + 1, Math.min(i + d + 1, N), 0, 0, N);if(ans < k * (t[0] - a[i])) {p++;ans = k * (t[0] - a[i]);m1 = i;m2 = t[1];}}if(p == 0) {System.out.println(0);} else {System.out.println(ans);System.out.print(m1 + " " + m2);}}public static void init(int n_) {int n = 1;while(n < n_) {n *= 2;}N = n;dat = new long[2 * N - 1][2];}public static void update(long k, long x) {int a = (int)(k + N - 1);dat[a][0] = x;dat[a][1] = k;while(a > 0) {a = (a - 1) / 2;if(dat[2 * a + 1][0] >= dat[2 * a + 2][0]) {dat[a][0] = dat[2 * a + 1][0];dat[a][1] = dat[2 * a + 1][1];} else {dat[a][0] = dat[2 * a + 2][0];dat[a][1] = dat[2 * a + 2][1];}}}public static long[] query(int a, int b, int k, int l, int r) {long[] ret = new long[2];if((r <= a) || (l >= b)) {ret[0] = 0;ret[1] = -1;return ret;}if((a <= l) && (r <= b)) {ret[0] = dat[k][0];ret[1] = dat[k][1];return ret;} else {long[] vl = query(a, b, 2 * k + 1, l, (l + r) / 2);long[] vr = query(a, b, 2 * k + 2, (l + r) / 2, r);if(vl[0] >= vr[0]) {ret[0] = vl[0];ret[1] = vl[1];} else {ret[0] = vr[0];ret[1] = vr[1];}return ret;}}}