fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. string s[100005];
  7. int B[100006],mi[100006],n,A[100006],l,r,k,mid,sum,m,sum2,ans;
  8. signed main(){
  9.     ios::sync_with_stdio(0);cin.tie(0);
  10.     cin>>n>>k;
  11.     for(int i=1; i<=n; i++){
  12.         cin>>A[i];
  13.     }
  14.     l=0;
  15.     r=1000'000'000;
  16.     while(l<=r){
  17.         mid=(l+r)/2;
  18.         for(int i=1; i<=n; i++){
  19.             B[i]=A[i]-mid;
  20.         }
  21.         sum=0;
  22.         for(int i=1; i<=n; i++){
  23.             sum+=B[i];
  24.             mi[i]=min(mi[i-1],sum);
  25.         }
  26.         m=1;
  27.         sum=0;
  28.         sum2=0;
  29.         bool OK=false;
  30.         for(int i=1; i<=n; i++){
  31.             sum+=A[i];
  32.             sum2+=B[i];
  33.             while(m<i && sum>=k && sum-A[m]>=k){
  34.                 sum-=A[m];
  35.                 m++;
  36.             }
  37.             if(sum>=k && sum2-mi[m-1]>=0){
  38.                 OK=true;
  39.             }
  40.         }
  41.         if(OK){
  42.             ans=mid;
  43.             l=mid+1;
  44.         }
  45.         else r=mid-1;
  46.     }
  47.     cout<<ans;
  48.  
  49.  
  50.     return 0;
  51. }
Success #stdin #stdout 0.01s 7328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EFBB4u
language:
C++14 (gcc 8.3)
created:
14 days ago
visibility:
public

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!