結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-04-05 00:11:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 1,000 ms |
コード長 | 2,177 bytes |
コンパイル時間 | 1,857 ms |
コンパイル使用メモリ | 175,592 KB |
実行使用メモリ | 10,232 KB |
最終ジャッジ日時 | 2024-07-19 23:46:17 |
合計ジャッジ時間 | 3,456 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i, x) for (int i = 0; i < x; ++i)#define rrep(i, x) for (int i = x-1; i >= 0; --i)using pii=pair<int,int>;const int inf = 3e18;struct segtree { // 区間min,maxint n;vector<pii> Max;vector<int> Min;void init(int n_) {n = 1;while (n < n_) n *= 2;Max.resize(2 * n);Min.resize(2 * n);for (int i = 0; i < 2 * n - 1; ++i) {Max[i] = pii(-inf, -inf);Min[i] = inf;}}void update(int idx, int val) {idx += n - 1;Min[idx] = val;Max[idx] = pii(val, -(idx - n + 1));while (idx > 0) {idx = (idx - 1) / 2;Min[idx] = min(Min[idx * 2 + 1], Min[idx * 2 + 2]);Max[idx] = max(Max[idx * 2 + 1], Max[idx * 2 + 2]);}}int get_min(int a, int b, int k = 0, int l = 0, int r = -1) { // [a, b)のminif (r == -1) r = n;if (r <= a || b <= l) return inf;if (a <= l && r <= b) return Min[k];int vl = get_min(a, b, k * 2 + 1, l, (l + r) / 2);int vr = get_min(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}pii get_max(int a, int b, int k = 0, int l = 0, int r = -1) { // [a, b)のmaxif (r == -1) r = n;if (r <= a || b <= l) return pii(-inf, -inf);if (a <= l && r <= b) return Max[k];pii vl = get_max(a, b, k * 2 + 1, l, (l + r) / 2);pii vr = get_max(a, b, k * 2 + 2, (l + r) / 2, r);return max(vl, vr);}};int x[100010];signed main(){int N,D,K;cin>>N>>D>>K;segtree seg;seg.init(N+1);rep(i, N) {cin>>x[i];seg.update(i, x[i]);}int ma = -inf;pii hoge;rep(i, N) {int a = x[i]*K;pii b = seg.get_max(i, min(i + 1 + D, N));if (ma < b.first*K - a) {ma = b.first*K - a;hoge.first = i, hoge.second = -b.second;}}if (ma <= 0) {cout << 0 << endl;return 0;}cout << ma << endl;cout << hoge.first << ' ' << hoge.second << endl;}