/ SB域 /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 6ms 308.0 KiB
#2 Accepted 1ms 220.0 KiB
#3 Accepted 1ms 216.0 KiB
#4 Accepted 2ms 344.0 KiB
#5 Accepted 9ms 1.469 MiB
#6 Accepted 17ms 2.586 MiB
#7 Accepted 27ms 3.797 MiB
#8 Accepted 34ms 5.012 MiB
#9 Accepted 43ms 6.578 MiB
#10 Accepted 35ms 7.762 MiB

代码

#include <cstdio>
#include <queue>
using namespace std;

int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0' || c>'9'){if (c=='-')f=-1;c=getchar();}
	while (c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return x*f;
}

const int MAXN=500005;
int n,x,y,ans=-99999999;
int a[MAXN],sum[MAXN],f[MAXN];
deque<int> Q;

int main()
{
	n=read();x=read();y=read();
	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i]=read());
	for (int i=1;i<=n;i++)
	{
		while (!Q.empty()&&sum[i-x]<sum[Q.back()])Q.pop_back();
		Q.push_back(i-x);
		while (!Q.empty()&&i-Q.front()>y)Q.pop_front();
		f[i]=sum[i]-sum[Q.front()];
		if (i>x)ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

信息

递交者
类型
递交
题目
【模板】最大子序和
题目数据
下载
语言
C++
递交时间
2019-05-04 11:32:47
评测时间
2019-05-04 11:32:47
评测机
分数
100
总耗时
179ms
峰值内存
7.762 MiB