結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-24 22:57:02 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 67 ms / 1,000 ms |
コード長 | 2,656 bytes |
コンパイル時間 | 1,067 ms |
コンパイル使用メモリ | 90,192 KB |
実行使用メモリ | 8,532 KB |
最終ジャッジ日時 | 2024-07-19 23:00:19 |
合計ジャッジ時間 | 3,009 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <algorithm>#include <cfloat>#include <climits>#include <cmath>#include <complex>#include <cstdio>#include <cstdlib>#include <cstring>#include <functional>#include <iostream>#include <map>#include <memory>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <utility>#include <vector>using namespace std;typedef long long ll;#define sz size()#define pb push_back#define mp make_pair#define fi first#define se second#define all(c) (c).begin(), (c).end()#define rep(i,a,b) for(ll i=(a);i<(b);++i)#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)#define clr(a, b) memset((a), (b) ,sizeof(a))#define ctos(c) string(1,c)#define print(x) cout<<#x<<" = "<<x<<endl;#define MOD 1000000007#define N_MAX (1<<20)#define INF 1000000000000LLint nn_mn;long long dat_mn[(2 * N_MAX) - 1];void init_mn(int n1){nn_mn = 1;while(nn_mn < n1)nn_mn *= 2;for(int i = 0; i < 2 * nn_mn - 1; i++){dat_mn[i] = INF;}}void update_mn(int k, long long a){k += nn_mn - 1;dat_mn[k] = a;while(k > 0){k = (k - 1) / 2;dat_mn[k] = min(dat_mn[k * 2 + 1], dat_mn[k * 2 + 2]);}}long long query_mn(int a, int b, int k, int l, int r){if(r <= a || b <= l)return INF;if(a <= l && r <= b){return dat_mn[k];}else{long long vl = query_mn(a, b, k * 2 + 1, l, (l + r) / 2);long long vr = query_mn(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}}int nn_mx;long long dat_mx[(2 * N_MAX) - 1];void init_mx(int n1){nn_mx = 1;while(nn_mx < n1)nn_mx *= 2;for(int i = 0; i < 2 * nn_mx - 1; i++){dat_mx[i] = -INF;}}void update_mx(int k, long long a){k += nn_mx - 1;dat_mx[k] = a;while(k > 0){k = (k - 1) / 2;dat_mx[k] = max(dat_mx[k * 2 + 1], dat_mx[k * 2 + 2]);}}long long query_mx(int a, int b, int k, int l, int r){if(r <= a || b <= l)return -INF;if(a <= l && r <= b){return dat_mx[k];}else{long long vl = query_mx(a, b, k * 2 + 1, l, (l + r) / 2);long long vr = query_mx(a, b, k * 2 + 2, (l + r) / 2, r);return max(vl, vr);}}int main() {ll n,d,k;cin>>n>>d>>k;vector<ll> v;init_mn(n);init_mx(n);rep(i,0,n){ll a;cin>>a;v.pb(a);update_mn(i,a);update_mx(i,a);}ll mx = 0;ll index = -1;rep(i,0,n-1){ll a = query_mx(i+1,min(n,i+d+1),0,0,nn_mx)-v[i];if(mx<a){mx = max(mx,a);index = i;}}if(mx==0){cout << 0 << endl;return 0;}ll index2 = -1;rep(i,index,n){if(v[i]-v[index]==mx){index2=i;break;}}cout << mx*k << endl;cout << index << " " << index2 << endl;return 0;}