fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int n;
  5. ll a[400001],pref[400001],x,pref1[400001];
  6. int bin(int l,int d,int i){  
  7. 	if(l==d)return l;
  8. 	if(l==d-1){
  9. 		if(pref[l]>i)
  10. 			return l;
  11. 		return d;
  12. 	}
  13. 	int mid=(l+d)/2;
  14. 	if(pref[mid]>i&&pref[mid-1]<=i)return mid;
  15. 	if(pref[mid]<=i)
  16. 		return bin(mid+1,d,i);
  17. 	return bin(l,mid-1,i);
  18. }
  19. ll resi(int i){
  20. 	if(pref[i]<x) 
  21. 		return -1;
  22. 	ll m=(a[i]+1)*a[i]/2ll;
  23. 	if(i==0){
  24. 		if(x>=a[0])
  25. 			return m;
  26. 		ll u=(a[0]-x)*(a[0]-x+1)/2ll;
  27. 		return m-u;
  28. 	}
  29. 	if(x==a[i]) return m;
  30. 	if(x<=a[i]){
  31. 		ll u=(a[i]-x)*(a[i]-x+1)/2ll;
  32. 		return m-u;
  33. 	}
  34. 	int mes=bin(0,i-1,pref[i]-x);
  35. 	ll trx=x-(pref[i]-pref[mes]);
  36. 	if(trx<0)return -1;  //this should not be negative but it sometimes is, i dont know why
  37. 	ll o=(a[mes]+1ll)*a[mes]/2ll,p=(a[mes]-trx)*(a[mes]-trx+1ll)/2ll;
  38. 	return pref1[i]-pref1[mes]+o-p;
  39. }
  40. int main(){
  41. 	cin>>n>>x;
  42. 	for(int i=0;i<n;i++)cin>>a[i];
  43. 	for(int i=n;i<2*n;i++)a[i]=a[i-n];
  44. 	n*=2;
  45. 	pref[0]=a[0];pref1[0]=a[0]*(a[0]+1)/2ll;
  46. 	for(int i=1;i<n;i++){pref[i]=pref[i-1]+a[i];pref1[i]=pref1[i-1]+a[i]*(a[i]+1)/2ll;}
  47. 	ll res=1;
  48. 	for(int i=0;i<n;i++)  //fixing the end and binary searching for the beginning
  49. 		res=max(res,resi(i));
  50. 	cout<<res;
  51. 	return 0;
  52. }
  53.  
Success #stdin #stdout 0s 4268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/rLE5jx
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!