結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-24 22:33:11 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 52 ms / 1,000 ms |
コード長 | 1,646 bytes |
コンパイル時間 | 1,372 ms |
コンパイル使用メモリ | 164,452 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-07-19 22:48:51 |
合計ジャッジ時間 | 3,382 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define int long longtypedef pair<int,int>pint;typedef vector<int>vint;typedef vector<pint>vpint;#define pb push_back#define mp make_pair#define fi first#define se second#define all(v) (v).begin(),(v).end()#define rep(i,n) for(int i=0;i<(n);i++)#define reps(i,f,n) for(int i=(f);i<(n);i++)#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}struct segtree{static const int SEG=1<<17;vector<pint>dat;segtree(vint &x):dat(SEG*2){for(int i=0;i<x.size();i++){dat[i+SEG-1].fi=x[i];}for(int i=0;i<SEG;i++){dat[i+SEG-1].se=i;}for(int i=SEG-2;i>=0;i--){dat[i]=min(dat[i*2+1],dat[i*2+2]);}}pint query(int a,int b,int k=0,int l=0,int r=SEG){if(r<=a||b<=l)return pint(INT_MAX,INT_MAX);if(a<=l&&r<=b)return dat[k];return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));}};signed main(){int N,D,K;cin>>N>>D>>K;vint X(N);rep(i,N)cin>>X[i];int ans=0;pint a;segtree seg(X);for(int i=1;i<N;i++){int l=max(0ll,i-D);pint p=seg.query(l,i);if(ans<X[i]-p.fi){ans=X[i]-p.fi;a=pint(p.se,i);}else if(ans==X[i]-p.fi){chmin(a,pint(p.se,i));}}if(ans==0)cout<<0<<endl;else{cout<<ans*K<<endl;cout<<a.fi<<" "<<a.se<<endl;}return 0;}