比赛 20240913练习 评测结果 AAAAAAAAAA
题目名称 数字游戏 最终得分 100
用户昵称 彭欣越 运行时间 0.478 s
代码语言 C++ 内存使用 8.65 MiB
提交时间 2024-09-13 21:15:42
显示代码纯文本
#include <bits/stdc++.h>
#define ls p*2
#define rs p*2+1
using namespace std;
typedef long long ll;
ll n,s,t,a[100010],sum[100010],res=-1e9;
struct node {
	ll l,r,v;
}tr[400010];
void build (int p,int l,int r) {
	tr[p].l=l,tr[p].r=r;
	if (l==r) {
		tr[p].v=sum[l];
		return;
	}
	int mid=(l+r)/2;
	build(ls,l,mid);
	build(rs,mid+1,r);
	tr[p].v=min(tr[ls].v,tr[rs].v);
}
ll query (int p,int l,int r) {
	if (tr[p].l>=l&&tr[p].r<=r) {
		return tr[p].v;
	}
	ll mid=(tr[p].l+tr[p].r)/2,sum=1e9;
	if (l<=mid) sum=min(sum,query(ls,l,r));
    if (r>mid) sum=min(sum,query(rs,l,r));
    return sum;
}
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];
    	sum[i]=sum[i-1]+a[i];
    }
    build(1,1,n);
    //res=sum[s];
    for (int i=s;i<=n;i++) {
    	res=max(res,sum[i]-query(1,i-t,i-s));
    }
    cout << res;
	return 0;
}