結果

問題 No.489 株に挑戦
ユーザー PulmnPulmn
提出日時 2017-02-24 23:07:03
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
5,248 KB
testcase_01 AC 31 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 50 ms
5,376 KB
testcase_17 AC 8 ms
5,376 KB
testcase_18 AC 29 ms
5,376 KB
testcase_19 AC 23 ms
5,376 KB
testcase_20 AC 55 ms
5,376 KB
testcase_21 AC 14 ms
5,376 KB
testcase_22 AC 6 ms
5,376 KB
testcase_23 AC 31 ms
5,376 KB
testcase_24 AC 63 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 55 ms
5,376 KB
testcase_27 AC 66 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 60 ms
5,376 KB
testcase_31 AC 62 ms
5,376 KB
testcase_32 AC 34 ms
5,376 KB
testcase_33 AC 62 ms
5,376 KB
testcase_34 AC 54 ms
5,376 KB
testcase_35 AC 22 ms
5,376 KB
testcase_36 AC 9 ms
5,376 KB
testcase_37 AC 32 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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