与世无争 @ 2019-11-05 00:12:39
自己下载数据自测过了,为什么洛谷评测机不让我过?
#pragma GCC optimize(2)
#include<cstdio>
inline int read() {
int n=0,w=1;
register char c=getchar();
while (c<'0'||c>'9') {
if (c=='-') w=-1;
c=getchar();
}
while (c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
return n*w;
}
int max(int q,int p) {
return (q>p)?q:p;
}
const int N=2000005;
int n,l,r,a[N],q[N][2],head,tail,f[N],ans=-1e9;
int main() {
n=read();
l=read();
r=read();
for (int i=0; i<=n; i++) a[i]=read();
for (int i=1; i<l; i++) f[i]=-1e9;
for (int i=l; i<=r; i++) {
f[i]=-1e9;
for (int j=i-l; j>=i-r; j--) f[i]=max(f[i],f[j]);
f[i]+=a[i];
}
for (int i=l; i<=r+1-l; i++) {
while (head<tail&&q[tail][0]<f[i]) tail--;
q[++tail][0]=f[i];
q[tail][1]=i;
}
for (int i=r+1; i<=n; i++) {
while (head<tail&&i-q[head+1][1]>r) head++;
f[i]=a[i]+q[head+1][0];
int k=i+1-l;
while (head<tail&&(q[tail][0]<f[k]||i-q[tail][1]>r)) tail--;
q[++tail][0]=f[k];
q[tail][1]=k;
}
for (int i=n-r+1; i<=n; i++) ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
//By与世无争
@苍空的蓝耀
@空气树
@LCA
@风之城008
@AC_duckling
@时间重洗
@改名真难QAQ
@青莲居士
by 欧鹰 @ 2019-11-05 07:27:59
建议在IDE跑一遍
by 艾恩葛朗特 @ 2019-11-05 21:24:41
@与世无争 大快人心
by 艾恩葛朗特 @ 2019-11-05 21:25:12
@与世无争 你现在过了吗
by 空气树 @ 2019-11-05 21:52:38
@与世无争 您现在多少分。
by 与世无争 @ 2019-11-05 22:18:18
@空气树 过了