fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5. int check(vector<int> &nums,vector<int> &arr,int l){
  6. 	int n=nums.size();
  7. 	vector<int> prefix(2*n+1,0);
  8. 	int op=0;
  9.  
  10. 	for(int i=0;i<n;i++){
  11.  
  12. 		if(i>0){
  13. 			prefix[i]=prefix[i] + prefix[i-1];
  14. 			nums[i]=nums[i]+prefix[i];
  15.  
  16. 		}
  17. 		if(arr[i]>nums[i]){
  18. 			int diff=arr[i]-nums[i];
  19. 			op=op+diff;
  20. 			prefix[i]=prefix[i]+diff;
  21. 			prefix[i+l]=prefix[i+l]-diff;
  22. 			nums[i]=nums[i] + diff;
  23. 		}
  24.  
  25. 	}
  26. 	return op;
  27.  
  28. }
  29. int main() {
  30. 	// your code goes here
  31. 	int n,m,l;
  32. 	cin>>n>>m>>l;
  33. 	vector<int> arr(n);
  34. 	int low= INT_MAX;
  35. 	int high = INT_MIN;
  36.  
  37.  
  38. 	for(int i=0;i<n;i++)
  39. 	{
  40. 		cin>>arr[i];
  41. 		low = min(low,arr[i]-m);
  42. 	    high = max(high,arr[i]);
  43.  
  44. 	}
  45. 	int ans=0;
  46.  
  47. 	while(low<=high){
  48. 		int mid = (low+high)/2;
  49. 		vector<int> nums(n,mid);
  50. 		if(check(nums,arr,l)<=m){
  51. 			ans=mid;
  52. 			high=mid-1;
  53. 		}
  54. 		else{
  55. 			low=mid+1;
  56.  
  57. 		}
  58. 	}
  59.  
  60. 	cout<<ans<<endl;
  61.  
  62.  
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 0.01s 5344KB
comments (?)
stdin
copy 
6 2 2
4 3 1 6 4 6
stdout
copy 
5
https://ideone.com/wu8i7v
language:
C++14 (gcc 8.3)
created:
7 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!