結果

問題 No.489 株に挑戦
ユーザー vjudge1
提出日時 2025-01-26 10:38:19
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 35 ms / 1,000 ms
コード長 1,620 bytes
コンパイル時間 1,686 ms
コンパイル使用メモリ 161,192 KB
実行使用メモリ 16,324 KB
最終ジャッジ日時 2025-01-26 10:38:23
合計ジャッジ時間 3,532 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=6e5;
const int mod=1e9+7;
struct  node{
	int l,r,maxn,id;
}tree[N];
int n,d,k,a[N];
void push_up(int p){
	tree[p].maxn=max(tree[p<<1].maxn,tree[p<<1|1].maxn);
	if(tree[p].maxn==tree[p<<1].maxn)tree[p].id=tree[p<<1].id;
	else tree[p].id=tree[p<<1|1].id;
}
void build(int p,int l,int r){
	tree[p].l=l;
	tree[p].r=r;
	if(l==r){
		tree[p].maxn=a[l];
		tree[p].id=l;
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
struct pos{
	int z,id;
};
pos qry(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r)return (pos){tree[p].maxn,tree[p].id};
	int ret=INT_MIN;
	int mid=tree[p].l+tree[p].r>>1;
	int idd=0;
	if(l<=mid){
		pos T=qry(p<<1,l,r);
		ret=T.z;
		idd=T.id;
	}
	if(r>mid){
		pos T=qry(p<<1|1,l,r);
		if(T.z>ret){
			ret=T.z;
			idd=T.id;
		}
	}
	return (pos){ret,idd};
}
int str,ed;
int ans;
signed main(){
//	freopen("stock.in","r",stdin);
//	freopen("stock.out","w",stdout);
	n=read(),d=read(),k=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,1,n);
	for(int i=1;i<=n;i++){
		pos zz=qry(1,min(i+1,n),min(i+d,n));
		int ret=(zz.z-a[i])*k;
		if(ret>ans){
			ans=ret;
			str=i;
			ed=zz.id;
		}
	}
	if(ans==0)cout<<0<<"\n";
	else cout<<ans<<"\n"<<str-1<<" "<<ed-1<<"\n";
    return 0;
}
0