比赛 20240913练习 评测结果 AAAAAAAAAA
题目名称 数字游戏 最终得分 100
用户昵称 dream 运行时间 0.462 s
代码语言 C++ 内存使用 7.23 MiB
提交时间 2024-09-13 21:19:48
显示代码纯文本
#include<bits/stdc++.h>
#define ls p*2
#define rs p*2+1
using namespace std;
typedef long long ll;
const int N=100005;
struct tree{
	int l,r;
	ll sum;
}tr[N*4];
ll a[N],qz[N];
ll n,s,t,ans=-0x7fffffff;
void pushup(int p){
	tr[p].sum=min(tr[ls].sum,tr[rs].sum);
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].sum=qz[l];
		return;
	}
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}
ll query(int p,int l,int r){
	if(l<=tr[p].l&&tr[p].r<=r){
		return tr[p].sum;
	}
	int mid=(tr[p].l+tr[p].r)/2;
	ll res=0x7fffffff;
	if(l<=mid){
		res=min(res,query(ls,l,r));
	}
	if(r>mid){
		res=min(res,query(rs,l,r));
	} 
	return res;
}
int main(){
	freopen("ggame.in","r",stdin);
	freopen("ggame.out","w",stdout);
	cin>>n>>s>>t;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		qz[i]+=a[i]+qz[i-1];
	}
	build(1,1,n);
	for(int i=s;i<=n;i++){
		ans=max(ans,qz[i]-query(1,i-t,i-s));
	}
	cout<<ans;
	return 0;
}