fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define rep(i, l, r) for ((i) = (l); (i) <=(r); (i)++)
  5. ll e[1000007];
  6. ll p1[1000007];
  7. ll p2[1000007];
  8. ll calculate(ll x,ll y)
  9. {
  10. 	ll s1=p1[y]-p1[x-1];
  11. 	ll k = abs(x-y)+1;
  12. 	ll s2= p2[y]-p2[x-1];
  13. 	ll sum=s2*k;
  14. 	ll answer = s1+sum;
  15. 	return answer;
  16. }
  17.  
  18. int main()
  19. {
  20. 	ios_base::sync_with_stdio(0);
  21. 	cin.tie(0);
  22. 	cout.tie(0);
  23. 	ll n;
  24. 	cin>>n;ll s;cin>>s;
  25. 	ll i;
  26. 	rep(i,1,n)
  27. 	{
  28. 		cin>>e[i];
  29. 		p1[i]=e[i]+p1[i-1];
  30. 		p2[i]=i+p2[i-1];
  31. 	}
  32. 	p2[n+1]=1e18;
  33. 	p1[n+1]=1e18;
  34.  
  35.  
  36. 	//cout<<"lol";
  37. 	///cout<<calculate(2,2);
  38. 	//cout<<"\n";
  39. 	ll ram=-1e18;
  40. 	rep(i,1,n)
  41. 	{
  42. 		ll low=i;
  43. 		ll high=n;
  44. 		ll answer = -1;ll km = 0 ;
  45. 	      while(low<=high && km==0)
  46. 	      {
  47.  
  48.  
  49.  
  50.                   ll mid=(low+high)/2;  
  51.  
  52.                   if(calculate(i,mid)>s)
  53.                   {
  54.                    high=mid-1;    
  55.                   }
  56.                   else{
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63.                       if(calculate(i,mid+1)<=s)
  64.                       {
  65.                       low=mid+1;
  66.                       }
  67.                       else
  68.                       {
  69.                       km=1;
  70.                       answer = mid;
  71.                       }    
  72.  
  73.  
  74.  
  75.                  }
  76.  
  77.  
  78.  
  79.           }
  80.  
  81. 		if(answer==-1)
  82. 		{
  83.  
  84.  
  85. 		}
  86. 		else
  87. 		{     ll real = abs(answer-i)+1;
  88.  
  89. 			ram=max(ram,real);
  90.  
  91. 		}
  92.  
  93.  
  94.  
  95. 	}
  96.  
  97.  
  98. 	cout<<ram  ;
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106. 	return 0;
  107.  
  108. }
Success #stdin #stdout 0s 4280KB
comments (?)
stdin
copy 
10 10
3 1 2 4 5 1 2 3 4 5
stdout
copy 
2
https://ideone.com/xcpv66
language:
C++14 (gcc 8.3)
created:
5 years 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!