[CF1358D] The Best Vacation - 双指针

[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;
}
上一篇:最少翻译者


下一篇:64匹马,8个赛道,找出前4名最少比赛多少场?