fork download 
  1. // author : anphung
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define int64 long long
  5. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  6. #define f0(i,a,b) for(int (i)=(a);(i)<=(b);++i)
  7. #define file(name) if(fopen(name".inp","r")){ freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
  8. #define maxn 100005
  9.  
  10. int n;
  11. int64 s;
  12. int a[maxn];
  13. int64 ans;
  14.  
  15. bool check(int mid){
  16. 	int64 cursum = 0;
  17. 	int64 sum = INT_MIN;
  18.  
  19. 	f0(i,0,mid-1){
  20. 		cursum += mid;
  21. 	}
  22. 	sum = max(cursum,sum);
  23.  
  24. 	f0(i,mid,n-mid){
  25. 		cursum += a[i] - a[i-mid];
  26. 		sum = max(sum,cursum);
  27. 	}
  28. 	return sum >= s;
  29. }
  30.  
  31. int32_t main(){
  32. 	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  33.  
  34. 	cin>>n>>s;	
  35. 	f0(i,0,n-1)cin>>a[i];
  36.  
  37. 	int lo = 1, hi = 5e5;
  38.  
  39. 	while(lo<=hi){
  40. 		int mid = lo + ((hi-lo)>>1);
  41. 		if(check(mid)){
  42. 			ans = mid;
  43. 			hi = mid - 1;
  44. 		}else lo = mid + 1;
  45. 	}
  46.  
  47. 	cout<<ans;
  48.  
  49. 	cerr << "time elapsed: "<<TIME <<"s.\n";
  50. }
Success #stdin #stdout #stderr 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
1
stderr 
time elapsed: 0.00441s.
https://ideone.com/38KXLK
language:
C++14 (gcc 8.3)
created:
10 hours 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!