思路
做这道题主要是需要发现一个性质：选择的区间必定是从某一个月的最后一天开始往前连续的一段区间。
考虑如何证明这个结论，设这个月有 \(x\) 天，假设有更优的方案满足到下一个月的第 \(y\) 天，则我们发现下一个月中的拥抱数为 \(\sum_{i=1}^{y} i\)，而显然任意一个长度为 \(y\) 的区间的最小拥抱数就是这个值，我们往前移动一定不劣于这个解。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+10;
int a[N],sum[N],qsum[N];
inline int check(int l,int r){return qsum[r]-qsum[l-1];}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,x;cin>>n>>x;int ans=0;
for (int i=1;i<=n;++i) cin>>a[i],qsum[i]=qsum[i-1]+a[i],sum[i]=sum[i-1]+(1+a[i])*a[i]/2;
for (int i=1;i<=n;++i) a[i+n]=a[i];
n<<=1;
for (int i=1;i<=n;++i) qsum[i]=qsum[i-1]+a[i],sum[i]=sum[i-1]+(1+a[i])*a[i]/2;
for (int i=(n/2);i<=n;++i){
int l=1,r=i;
while (l<r){
if (l+1==r){if (check(r,i)<=x);else l=r;break;}
int mid=(l+r)>>1;
if (check(mid,i)<=x) r=mid-1;
else l=mid;
}
++l;
int q=x-(qsum[i]-qsum[l-1]);
int summ;
if (l>i+1) summ=0;
else summ=sum[i]-sum[l-1]+(a[l-1]+(a[l-1]-q+1))*q/2;
ans=max(ans,summ);
}
cout<<ans<<'\n';
return 0;
}