結果
| 問題 |
No.489 株に挑戦
|
| コンテスト | |
| ユーザー |
 suigingin
|
| 提出日時 | 2017-02-24 23:43:56 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 358 ms / 1,000 ms |
| コード長 | 6,724 bytes |
| コンパイル時間 | 3,115 ms |
| コンパイル使用メモリ | 91,140 KB |
| 実行使用メモリ | 58,500 KB |
| 最終ジャッジ日時 | 2024-07-19 23:13:05 |
| 合計ジャッジ時間 | 13,262 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
import java.util.Arrays;
import java.util.Scanner;
public class Main {
MyScanner sc = new MyScanner();
Scanner sc2 = new Scanner(System.in);
long start = System.currentTimeMillis();
long fin = System.currentTimeMillis();
final int MOD = 1000000007;
int[] dx = { 1, 0, 0, -1 };
int[] dy = { 0, 1, -1, 0 };
int n, q;
Pair dat[];
void init() {
dat = new Pair[n * 2 - 1];
for (int i = 0; i < n * 2 - 1; i++) {
dat[i] = new Pair(0, 0);
}
}
Pair query(int a, int b, int k, int l, int r) {
if (a <= l && r <= b) return dat[k];
if (r <= a || b <= l) return new Pair(0, 0);
Pair vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
Pair vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
if (vl.cnt < vr.cnt) return vr;
else return vl;
}
void update(int i, Pair x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2;
dat[i] = dat[i * 2 + 1].cnt < dat[i * 2 + 2].cnt ? dat[i * 2 + 2] : dat[i * 2 + 1];
}
}
void display() {
StringBuilder sb = new StringBuilder();
int h = 0;
int index = 0;
while (index < dat.length) {
for (int i = 0; i < Math.pow(2, h); i++)
sb.append(dat[index++].cnt + " ");
sb.append("\n");
h++;
}
System.out.print(sb);
}
void run() {
int N = sc.nextInt();
int D = sc.nextInt();
long K = sc.nextLong();
long[] X = sc.nextLongArray(N);
int nn = N;
n = 1;
while (n < nn) n *= 2;
init();
for (int i = 0; i < N; i++) {
update(i, new Pair(X[i], i));
}
long ans = 0;
int day = 0;
int day2 = 0;
for (int i = 0; i < N; i++) {
Pair max = query(i, i + D + 1, 0, 0, n);
if (ans < (max.cnt - X[i]) * K) {
ans = (max.cnt - X[i]) * K;
day = i;
day2 = max.day;
}
}
if(ans == 0) {
System.out.println(ans);
return;
}
System.out.println(ans);
System.out.println(day+" "+day2);
}
class Pair {
long cnt;
int day;
public Pair(long cnt, int day) {
super();
this.cnt = cnt;
this.day = day;
}
void show() {
System.out.println("cnt = " + this.cnt + " day = " + this.day);
}
}
public static void main(String[] args) {
new Main().run();
}
void debug(Object... o) {
System.out.println(Arrays.deepToString(o));
}
void debug2(int[][] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
System.out.print(array[i][j]);
}
System.out.println();
}
}
boolean inner(int h, int w, int limH, int limW) {
return 0 <= h && h < limH && 0 <= w && w < limW;
}
void swap(int[] x, int a, int b) {
int tmp = x[a];
x[a] = x[b];
x[b] = tmp;
}
// find minimum i (k <= a[i])
int lower_bound(int a[], int k) {
int l = -1;
int r = a.length;
while (r - l > 1) {
int mid = (l + r) / 2;
if (k <= a[mid])
r = mid;
else
l = mid;
}
// r = l + 1
return r;
}
// find minimum i (k < a[i])
int upper_bound(int a[], int k) {
int l = -1;
int r = a.length;
while (r - l > 1) {
int mid = (l + r) / 2;
if (k < a[mid])
r = mid;
else
l = mid;
}
// r = l + 1
return r;
}
long gcd(long a, long b) {
return a % b == 0 ? b : gcd(b, a % b);
}
long lcm(long a, long b) {
return a * b / gcd(a, b);
}
boolean palindrome(String s) {
for (int i = 0; i < s.length() / 2; i++) {
if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
}
return true;
}
class MyScanner {
int nextInt() {
try {
int c = System.in.read();
while (c != '-' && (c < '0' || '9' < c))
c = System.in.read();
if (c == '-')
return -nextInt();
int res = 0;
do {
res *= 10;
res += c - '0';
c = System.in.read();
} while ('0' <= c && c <= '9');
return res;
} catch (Exception e) {
return -1;
}
}
double nextDouble() {
return Double.parseDouble(next());
}
long nextLong() {
return Long.parseLong(next());
}
String next() {
try {
StringBuilder res = new StringBuilder("");
int c = System.in.read();
while (Character.isWhitespace(c))
c = System.in.read();
do {
res.append((char) c);
} while (!Character.isWhitespace(c = System.in.read()));
return res.toString();
} catch (Exception e) {
return null;
}
}
int[] nextIntArray(int n) {
int[] in = new int[n];
for (int i = 0; i < n; i++) {
in[i] = nextInt();
}
return in;
}
int[][] nextInt2dArray(int n, int m) {
int[][] in = new int[n][m];
for (int i = 0; i < n; i++) {
in[i] = nextIntArray(m);
}
return in;
}
double[] nextDoubleArray(int n) {
double[] in = new double[n];
for (int i = 0; i < n; i++) {
in[i] = nextDouble();
}
return in;
}
long[] nextLongArray(int n) {
long[] in = new long[n];
for (int i = 0; i < n; i++) {
in[i] = nextLong();
}
return in;
}
char[][] nextCharField(int n, int m) {
char[][] in = new char[n][m];
for (int i = 0; i < n; i++) {
String s = sc.next();
for (int j = 0; j < m; j++) {
in[i][j] = s.charAt(j);
}
}
return in;
}
}
}