結果

問題 No.489 株に挑戦
ユーザー Pulmn
提出日時 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;
      |                                ^~~

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0