D. The Best Vacation

大致题意:规定一个日历有图片说明 个月,每个月有图片说明 天,在第图片说明 个月的第图片说明 天活动你可以获得图片说明 的贡献,你只能连续图片说明 天活动,请问你能获得的最大贡献是多少.
图片说明

分析:
方法一:尺取法.
考虑我们选的天数是连续,那么对应月份也是连续的,并且假设中间月份的天数都是取得到的,但是还可以再两边去取天数,显然我们应该是去最左边的天数,因为贡献是从图片说明 开始递减的,而右边的天数是从图片说明 开始递增的。
那么我们依次遍历月份,用双指针去维护可满足的连续天数并计算对应贡献.
但是月份天数就跟环一样,是首尾相接的,对于环而言的尺取,我们一般都是多开一倍空间,数组循环一遍,然后从 的位置开始计算贡献(这样可以算得当前选择方案是部分最优).维护连续天数我们可以用两个前缀和进行维护。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=2e5+10;

int n; 
ll x,a[maxn<<1],sum1[maxn<<1],sum2[maxn<<1],ans;

int main()
{
    scanf("%d%lld",&n,&x);
    for( int i=1;i<=n;i++ ) scanf("%lld",&a[i]),a[n+i]=a[i];
    for( int i=1;i<=2*n;i++ )
    {
        sum1[i]=sum1[i-1]+a[i];
        sum2[i]=sum2[i-1]+a[i]*(a[i]+1)/2;
    }
    int j=0;
    for( int i=1;i<=2*n;i++ )
    {
        while( sum1[i]-sum1[j]>x ) ++j;
        if( i>n )
        {
            ll val=sum2[i]-sum2[j];
            ll l=x-(sum1[i]-sum1[j]);
            val+=(a[j]-l+1+a[j])*l/2;
            ans=max(ans,val);
        }
    }
    printf("%lld\n",ans);
    return 0;
}