[CF1358D] The Best Vacation - 双指针

Description

一年有 \(n\) 个月，第 \(i\) 个月有 \(a_i\) 天，在每个月的第 \(j\) 天你将得到 \(j\) 个拥抱。你想要和某人待在一起 \(x\) 天（连续），求最多能得到多少个拥抱。

Solution

当我们选择的结尾是一个月的最后一天时，显然不会使得答案更劣，因此我们枚举选择的结尾是哪一天，这样可能的情况只有 n 种，预处理前缀和后用双指针维护即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1e+6+5;
const int M = 1e+3+5;
const int mod1 = 1e+9+7;
const int mod2 = 998244353;

#define dbg(x) cerr<<#x<<":"<<x<<endl

signed main()
{
	ios::sync_with_stdio(false);
	
	vector <int> sum(N+2);
	for(int i=1;i<=N;i++) sum[i]=sum[i-1]+i;

	int n,x;
	cin>>n>>x;

	vector <int> d(N+2);

	for(int i=1;i<=n;i++) cin>>d[i];

	int p=n;
	int tmp=0;
	int ans=0;

	for(int i=n;i>=1;i--)
	{
		while(x>0)
		{
			x-=d[p];
			tmp+=sum[d[p]];
			--p;
			if(p==0) p=n;		
		}
		ans=max(ans,tmp+x*(1-x)/2);
		tmp-=sum[d[i]];
		x+=d[i];
	}

	cout<<ans<<endl;
	
	return 0;
}