結果
問題 | No.489 株に挑戦 |
ユーザー |
![]() |
提出日時 | 2017-02-24 23:07:03 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 66 ms / 1,000 ms |
コード長 | 2,240 bytes |
コンパイル時間 | 1,355 ms |
コンパイル使用メモリ | 90,400 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 23:02:23 |
合計ジャッジ時間 | 3,375 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:111:37: warning: ‘l’ may be used uninitialized in this function [-Wmaybe-uninitialized] 111 | else cout<<M<<endl<<j<<' '<<l<<endl; | ^ main.cpp:111:32: warning: ‘j’ may be used uninitialized in this function [-Wmaybe-uninitialized] 111 | else cout<<M<<endl<<j<<' '<<l<<endl; | ^~~
ソースコード
#include <iostream>#include <fstream>#include <typeinfo>#include <vector>#include <stack>#include <cmath>#include <set>#include <map>#include <string>#include <algorithm>#include <cstdio>#include <queue>#include <iomanip>#include <cctype>#define syosu(x) fixed<<setprecision(x)using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> P;typedef pair<double,double> pdd;typedef pair<ll,ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<double> vd;typedef vector<vd> vvd;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<string> vs;typedef vector<bool> vb;typedef vector<vb> vvb;typedef vector<P> vp;typedef vector<vp> vvp;typedef vector<pll> vpll;typedef pair<int,P> pip;typedef vector<pip> vip;const int inf=1<<30;const ll INF=1ll<<52;const double pi=acos(-1);const double eps=1e-8;const ll mod=1e9+7;const vi emp;const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,-0};const int DX[8]={-1,-1,-1,0,0,1,1,1},DY[8]={1,0,-1,1,-1,1,0,-1};class RMQ_Index{private:vp rmq;P Query_func(int a,int b,int k,int l,int r){if(r<=a||b<=l) return {-1,0};if(a<=l&&r<=b) return rmq[k];else{int mid=(l+r)/2;P vl=Query_func(a,b,k*2+1,l,mid);P vr=Query_func(a,b,k*2+2,mid,r);if(vl.first==vr.first) return (vl.second<vr.second?vl:vr);return (vl>vr)?vl:vr;}}public:int n;void Init(int n_){n=1;while(n<n_) n*=2;rmq=vp(2*n-1,{-1,0});for(int i=0;i<n;i++) rmq[i+n-1].second=i;}void Update(int k,int x){k+=n-1;rmq[k].first=x;while(k>0){k=(k-1)/2;P L=rmq[k*2+1],R=rmq[k*2+2];if(L.first==R.first) rmq[k]=L.second<R.second?L:R;else rmq[k]=L>R?L:R;}}P Query(int a,int b){return Query_func(a,b,0,0,n);}int Open(int k){return rmq[k+n-1].first;}};int n,d;ll k;int main(){cin>>n>>d>>k;RMQ_Index rmq;rmq.Init(n);for(int i=0;i<n;i++){int t;cin>>t;rmq.Update(i,t);}ll M=-INF;int j,l;for(int i=0;i<n-1;i++){P p=rmq.Query(i,min(n,i+d+1));ll res=k*((ll)p.first-rmq.Open(i));if(M<res){M=res;j=i;l=p.second;}}if(M==0) cout<<0<<endl;else cout<<M<<endl<<j<<' '<<l<<endl;}