Aakkosetsumussa @ 2023-07-17 10:52:59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,l,r,a[30000000],m[30000000],mx=-0x3f3f3f3f,q[30000000],head=1,tail=1;
int main() {
scanf("%lld %lld %lld",&n,&l,&r);
for(ll i=0; i<=n; i++)
scanf("%lld",&a[i]);
for(ll i=l; i<=n; i++) {
while(head<=tail&&m[q[tail]]<=m[i-l])
tail--;
q[++tail]=i-l;
while(q[head]+r<i)
head++;
m[i]=m[q[head]]+a[i];
}
for(ll i=n+1-r; i<=n; i++)
mx=max(mx,m[i]);
printf("%lld\n",mx);
return 0;
}
by Qwdb @ 2023-08-11 10:34:12
需要把dp数组初始化为极小值。
就是在开头加上:
memset(m, 0xcf, sizeof m);
m[0] = 0;
不妨试试这组hack数据:
10 5 6
0 10 2 13 24 -5 -6 1 0 3 -1
正确答案应该是5
by Qwdb @ 2023-08-11 10:34:45
啊不对正确答案是-5
by Qwdb @ 2023-08-11 10:37:03
哦然而你用的是long long,那就不能memset了,就for循环赋一个极小值就好了
by Qwdb @ 2023-08-11 10:38:46
酱紫
for(int i=1;i<=3000000;i++)
{
m[i]=-2147483648;
}
by littlebug @ 2023-08-17 18:59:18
可以memset吧
memset(m,-0x3f,sizeof(m));