Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
- const ll mod = 1e9+7;
- int bs(int c_idx, ll x, vector<ll> &pre, int n){
- int l = c_idx, r = 2*n, ans = -1;
- while(l<=r){
- int m = l + (r-l)/2;
- // cout<<"m: "<<m;
- if(x == pre[m] - pre[c_idx-1]){
- return m;
- }
- else if(x < pre[m] - pre[c_idx-1]){
- // cout<<" y: "<<m<<endl;
- r = m-1;
- }
- else{
- ans = m;
- l = m+1;
- // cout<<" n: "<<m<<endl;
- }
- }
- return ans;
- }
- int bins(ll space, int c_idx, int e_idx, vector<ll> &pre){
- int l = c_idx, r = e_idx, ans = -1;
- while(l<=r){
- int m = l + (r-l)/2;
- if(space >= pre[e_idx] - pre[m-1]){
- ans = m;
- r = m-1;
- }
- else{
- l = m+1;
- }
- }
- return ans;
- }
- int solve(){
- ll n,x;cin>>n>>x;
- vector<ll> d(n+1,0);
- vector<ll> pre(2*n+2, 0);
- vector<ll> mpre(2*n + 2, 0);
- for(int i=1;i<=n;++i){
- cin>>d[i];
- }
- d[0] = d[n], pre[0] = d[0], mpre[0] = (d[0]*(d[0]+1))/2;
- for(int i=1;i<=n;++i){
- pre[i] = pre[i-1] + d[i];
- mpre[i] = mpre[i-1] + (d[i]*(d[i]+1))/2;
- }
- for(int i=n+1;i<=n+n;++i){
- pre[i] = pre[i-1] + d[i-n];
- mpre[i] = mpre[i-1] + (d[i-n]*(d[i-n]+1))/2;
- }
- for(ll i=1;i<=n;++i){
- int idx = bs(i, x, pre, n);
- int p = idx;
- ll rest = x - (pre[idx] - pre[i-1]);
- if(x <= d[i]){
- ans = max(ans, (d[i]*(d[i]+1))/2 - ((d[i]-x)*(d[i]-x+1))/2);
- continue;
- }
- if(rest >= d[i-1]){
- ll sum = mpre[idx] - mpre[i-1] + (rest*(rest+1))/2;
- ans = max(ans, sum);
- return 0;
- }
- else{
- int p = bins(d[i-1]-rest, i, idx, pre);
- if(p!=-1){
- ll sum = mpre[p-1] - mpre[i-1] + (d[i-1]*(d[i-1]+1))/2 - ((d[i-1]-(rest+pre[idx]-pre[p-1]))*(d[i-1]-(rest+pre[idx]-pre[p-1])+1))/2;
- ans = max(sum, ans);
- }
- else{
- ll sum = mpre[idx] - mpre[i-1] + (d[i-1]*(d[i-1]+1))/2 - ((d[i-1]-rest)*(d[i-1]-rest+1))/2;
- ans = max(ans, sum);
- }
- }
- }
- cout<<ans;
- return 0;
- }
- int main(){
- fast;
- int t=1;
- //cin>>t;
- while(t--){
- solve();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment