結果

問題 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;
}
0