fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24.  
  25.  
  26.  
  27. vector<int> a;
  28.  
  29. pair<int,int> getMaxSubarraySum(int n, int d, double mean){
  30.  
  31. 	// Subtract a small epsilon to handle precision loss
  32. 	mean = mean - 1e-12;
  33.  
  34. 	vector<double> t(n);
  35. 	for(int i=0; i<n; i++){
  36. 		t[i] = a[i] - mean;
  37. 	}
  38.  
  39. 	vector<double> prefix(n);
  40. 	double sum = 0;
  41.  
  42. 	double mini = 0;
  43. 	int miniI = -1;
  44.  
  45. 	for(int i=0; i<n; i++){
  46. 		sum += t[i];
  47.  
  48. 		if(i-d>=-1){
  49. 			double lastSum = i-d==-1 ? 0 : prefix[i-d];
  50. 			if(lastSum < mini){
  51. 				mini = lastSum;
  52. 				miniI = i-d;
  53. 			}
  54.  
  55. 			double maxSum = sum - mini;
  56.  
  57. 			if(maxSum >= 0){
  58. 				return {miniI+2, i+1 };
  59. 			}
  60. 		}
  61.  
  62. 		prefix[i] = sum;
  63. 	}
  64.  
  65. 	return {1, 1+d};
  66. }
  67.  
  68.  
  69. bool isPossible(int n, int d, double mid){
  70. 	vector<double> transformed(n);
  71. 	for(int i=0; i<n; i++){
  72. 		transformed[i] = a[i] - mid;
  73. 	}
  74.  
  75. 	vector<double> prefix(n);
  76.  
  77. 	double sum = 0;
  78. 	double maxSum = -INF;
  79.  
  80. 	double mini = 0; //* Null == 0 for prefix Sum
  81. 	// double mini = INF; //* Not suited here
  82.  
  83. 	for(int i=0; i<n; i++){
  84. 		sum += transformed[i];
  85.  
  86. 		if(i-d>=-1){
  87. 			double lastSum = i-d==-1 ? 0 : prefix[i-d];
  88. 			mini = min(mini, lastSum);
  89.  
  90. 			maxSum = max(maxSum, sum-mini);
  91. 		}
  92. 		prefix[i] = sum;
  93. 	}
  94.  
  95. 	return maxSum >= 0;
  96. }
  97.  
  98.  
  99.  
  100. pair<int,int> consistency(int n, int d){
  101.  
  102. 	double s = -INF;
  103. 	double e = INF;
  104.  
  105. 	double maxMean = 0;
  106.  
  107. 	for(int i=1; i<=100; i++){
  108. 		double mid = s + (e-s)/2;
  109.  
  110. 		if(isPossible(n, d, mid)){
  111. 			maxMean = mid;
  112. 			s = mid;
  113. 		}
  114. 		else e = mid;
  115.  
  116. 	}
  117.  
  118.  
  119. 	auto indices =  getMaxSubarraySum(n, d, maxMean);
  120.  
  121. 	return indices;
  122. }
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140. pair<int,int> practice(int n, int d){
  141.  
  142. 	return {};
  143.  
  144. }
  145.  
  146.  
  147.  
  148.  
  149.  
  150. void solve() {
  151.  
  152.     int n, d;
  153.     cin>>n>>d;
  154.     a.resize(n);
  155.  
  156.     for(int i=0; i<n; i++) cin >> a[i];
  157.  
  158. 	auto ans1 = consistency(n, d);
  159.  
  160. 	cout << ans1.first << " " << ans1.second << endl;
  161.  
  162.  
  163. 	// auto p = practice(n, d);
  164. 	// cout << ans1.first << " " << ans1.second  << " -> " << p.first << " " << p.second << endl;
  165.  
  166. }
  167.  
  168.  
  169.  
  170.  
  171.  
  172. int32_t main() {
  173.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  174.  
  175.     int t = 1;
  176.     while (t--) {
  177.         solve();
  178.     }
  179.  
  180.     return 0;
  181. }
  182.  
  183.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6 2
3 1 8 5 7 2
stdout
copy 
3 5
https://ideone.com/83XjEP
language:
C++14 (gcc 8.3)
created:
22 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!