結果

問題 No.489 株に挑戦
ユーザー vjudge1
提出日時 2025-01-26 10:32:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 57 ms / 1,000 ms
コード長 1,088 bytes
コンパイル時間 1,596 ms
コンパイル使用メモリ 161,860 KB
実行使用メモリ 14,700 KB
最終ジャッジ日時 2025-01-26 10:32:19
合計ジャッジ時間 4,234 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:37:39: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
   37 |         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                                      ~^  ~~~~~
      |                                       |  |
      |                                       |  long long int*
      |                                       int*
      |                                      %lld
main.cpp:37:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                               ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r;
	long long t,num;
}tree[400005];
long long n,d,k,ans=0,ansn,ansm,a[400005];
void pushup(int rt){
	tree[rt].t=max(tree[2*rt].t,tree[2*rt+1].t);
	tree[rt].num=(tree[rt].t==tree[2*rt].t)?tree[2*rt].num:tree[2*rt+1].num;
}
void build(int rt,int l,int r){
	tree[rt].l=l;
	tree[rt].r=r;
	if(l==r){
		tree[rt].t=a[l];
		tree[rt].num=l;
		return; 
	}build(2*rt,l,(l+r)/2);
	build(2*rt+1,(l+r)/2+1,r);
	pushup(rt);
}
node cha(int rt,int L,int R){
	if(L<=tree[rt].l&&R>=tree[rt].r) return tree[rt];
	node kk;kk.t=-2147483647;
	int mid=(tree[rt].r+tree[rt].l)/2;
	if(L<=mid) kk=cha(rt*2,L,R);
	if(R>=mid+1){
		node ch=cha(rt*2+1,L,R);
		if(ch.t>kk.t) kk=ch;
	}return kk;
} 
int main(){
//	freopen("stock.in","r",stdin);
//	freopen("stock.out","w",stdout);
	cin>>n>>d>>k;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=n-1;i++){
		node nd=cha(1,i+1,min(i+d,n));
		if(ans<nd.t-a[i]){
			ans=nd.t-a[i];
			ansn=i-1;
			ansm=nd.num-1;
		}
	}if(ans==0){cout<<0;return 0;}
	cout<<ans*k<<"\n"<<ansn<<" "<<ansm;
}
0