aj30

Untitled

May 30th, 2020
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.                      
  5. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  6. const ll mod = 1e9+7;
  7.  
  8. int bs(int c_idx, ll x, vector<ll> &pre, int n){
  9.  
  10.     int l = c_idx, r = 2*n, ans = -1;
  11.     while(l<=r){
  12.         int m = l + (r-l)/2;
  13.         // cout<<"m: "<<m;
  14.         if(x == pre[m] - pre[c_idx-1]){
  15.             return m;
  16.         }
  17.         else if(x < pre[m] - pre[c_idx-1]){
  18.             // cout<<" y: "<<m<<endl;
  19.            
  20.             r = m-1;
  21.         }
  22.         else{
  23.             ans = m;
  24.             l = m+1;
  25.             // cout<<" n: "<<m<<endl;
  26.         }
  27.     }
  28.     return ans;
  29. }
  30. int bins(ll space, int c_idx, int e_idx, vector<ll> &pre){
  31.     int l = c_idx, r = e_idx, ans = -1;
  32.     while(l<=r){
  33.         int m = l + (r-l)/2;
  34.         if(space >= pre[e_idx] - pre[m-1]){
  35.             ans = m;
  36.             r = m-1;
  37.         }
  38.         else{
  39.             l = m+1;
  40.         }
  41.     }
  42.     return ans;
  43. }
  44. int solve(){
  45.     ll n,x;cin>>n>>x;
  46.     vector<ll> d(n+1,0);
  47.     vector<ll> pre(2*n+2, 0);
  48.     vector<ll> mpre(2*n + 2, 0);
  49.    
  50.     for(int i=1;i<=n;++i){
  51.         cin>>d[i];
  52.     }
  53.     d[0] = d[n], pre[0] = d[0], mpre[0] = (d[0]*(d[0]+1))/2;
  54.     for(int i=1;i<=n;++i){
  55.         pre[i] = pre[i-1] + d[i];
  56.         mpre[i] = mpre[i-1] + (d[i]*(d[i]+1))/2;
  57.     }
  58.    
  59.     for(int i=n+1;i<=n+n;++i){
  60.         pre[i] = pre[i-1] + d[i-n];
  61.         mpre[i] = mpre[i-1] + (d[i-n]*(d[i-n]+1))/2;
  62.     }
  63.  
  64.     for(ll i=1;i<=n;++i){
  65.         int idx = bs(i, x, pre, n);
  66.        
  67.         int p = idx;
  68.         ll rest = x - (pre[idx] - pre[i-1]);
  69.         if(x <= d[i]){
  70.             ans = max(ans, (d[i]*(d[i]+1))/2 - ((d[i]-x)*(d[i]-x+1))/2);
  71.             continue;
  72.         }
  73.  
  74.         if(rest >= d[i-1]){
  75.             ll sum = mpre[idx] - mpre[i-1] + (rest*(rest+1))/2;
  76.             ans = max(ans, sum);
  77.             return 0;
  78.         }
  79.         else{
  80.             int p = bins(d[i-1]-rest, i, idx, pre);
  81.             if(p!=-1){
  82.                 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;
  83.                 ans = max(sum, ans);
  84.             }
  85.             else{
  86.                 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;
  87.                 ans = max(ans, sum);
  88.             }
  89.            
  90.            
  91.         }
  92.        
  93.     }
  94.     cout<<ans;
  95.     return 0;
  96. }
  97.  
  98. int main(){
  99.     fast;
  100.     int t=1;
  101.     //cin>>t;
  102.     while(t--){
  103.         solve();
  104.     }
  105.  
  106.     return 0;
  107. }
Add Comment
Please, Sign In to add comment