求调玄关30pts
查看原帖
求调玄关30pts
1307045
Dark__Dream楼主2025/7/31 10:09
#include<bits/stdc++.h>
using namespace std;
long long n,k,e[2000001],sum[2100001],dp[2100001][2];
long long q[2100001];
int main()
{
    cin>>n>>k;
    for(long long i=1;i<=n;i++)
        cin>>e[i],sum[i]=sum[i-1]+e[i];
    long long head=1,tail=1;
    for(long long i=1;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        while(q[head]<i-k&&head<=tail)head++;
        dp[i][1]=dp[q[head]][0]+sum[i]-sum[q[head]];
        while(dp[i][0]-sum[i]>dp[q[head]][0]-sum[q[head]]&&head<=tail)tail--;
        q[++tail]=i;
    }
    cout<<max(dp[n][0],dp[n][1]);
}
2025/7/31 10:09
加载中...