結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-25 10:18:13 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,309 bytes |
コンパイル時間 | 1,284 ms |
コンパイル使用メモリ | 160,800 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-11 14:53:50 |
合計ジャッジ時間 | 3,446 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 WA * 21 |
ソースコード
#include<bits/stdc++.h>#define range(i,a,b) for(int i = (a); i < (b); i++)#define rep(i,b) for(int i = 0; i < (b); i++)#define all(a) (a).begin(), (a).end()#define show(x) cerr << #x << " = " << (x) << endl;#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;const int INF = 2000000000;using namespace std;const int MAX_N = 1 << 17;//セグメントツリーを持つ配列int n, dat[2 * MAX_N - 1][2];void init(int n_){n = 1;while(n < n_) n *= 2;rep(i,2 * n - 1) dat[i][0] = 0;}void update(int k, int a, int b){//葉の節点k += n - 1;dat[k][0] = a;dat[k][1] = b;//登りながら更新while(k > 0){k = (k - 1) / 2;if(dat[k * 2 + 1][0] > dat[k * 2 + 2][0]){dat[k][0] = dat[k * 2 + 1][0];dat[k][1] = dat[k * 2 + 1][1];}else if(dat[k * 2 + 1][0] < dat[k * 2 + 2][0]){dat[k][0] = dat[k * 2 + 2][0];dat[k][1] = dat[k * 2 + 2][1];}}}//[a, b)の最小値を求める//query(a, b, 0, 0, n)pair<int, int> query(int a, int b, int k, int l, int r){//cout << a << ' ' << b << ' ' << k << ' ' << l << ' ' << r << endl;//[a, b) と[l, r)が交差しなければ、INT_MAXif(r <= a || b <= l) return make_pair(0,-1);//[a,b)が[l,r)を完全に含んでいれば、この節点の値if(a <= l && r <= b) return make_pair(dat[k][0], dat[k][1]);else{//そうでなければ、2つのこの最小値pair<int, int> vl = query(a, b, k * 2 + 1, l, ( l + r) / 2);pair<int, int> vr = query(a, b, k * 2 + 2, (l + r) / 2, r);if(vl.first > vr.first) return vl;else return vr;}}int main(){int n, d, k;int x[100005];cin >> n >> d >> k;init(n);rep(i,n){cin >> x[i];update(i,x[i],i);}long long maxi = 0;pair<int, int> day;rep(i,n - 1){pair<int, int> p;int dif;p = query(i,min(i + d,n), 0, 0, n);dif = p.first - x[i];if(dif > maxi){maxi = dif;day.first = i;day.second = p.second;}}cout << k * maxi << endl;if(k * maxi > 0) cout << day.first << ' ' << day.second << endl;}