fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. void minimize(T& a, const T& b) {
  13. 	if (b < a) a = b; 
  14. }
  15.  
  16. template<typename T>
  17. void maximize(T& a, const T& b) {
  18. 	if (a < b) a = b;  
  19. }
  20.  
  21. const int N = 15e3 + 5; 
  22.  
  23. int n, k; 
  24. int a[N];  
  25. int pref[N];  
  26.  
  27. int f[N]; // f[i] = Số đoạn nhỏ nhất (min_k) có thể chia khi xét đoạn [1, i]
  28. int g[N]; // g[i] = Số đoạn lớn nhất (max_k) có thể chia khi xét đoạn [1, i]
  29.  
  30. struct FenwickMin {
  31. 	int n;  
  32. 	vector<int> ft;  
  33.  
  34. 	FenwickMin(int n) : n(n) {
  35. 		ft.resize(n, INF); 
  36. 	}
  37.  
  38. 	void update(int pos, int val) {
  39. 		for (; pos >= 0; pos = (pos & (pos + 1)) - 1) {
  40. 			minimize(ft[pos], val); 
  41. 		}
  42. 	}
  43.  
  44. 	int get(int pos) {
  45. 		int ans = INF;  
  46. 		for (; pos < n; pos = pos | (pos + 1)) {
  47. 			minimize(ans, ft[pos]);
  48. 		}
  49. 		return ans; 
  50. 	}
  51. };
  52.  
  53. struct FenwickMax {
  54. 	int n; 
  55. 	vector<int> ft; 
  56.  
  57. 	FenwickMax(int n) : n(n) {
  58. 		ft.resize(n, -INF); 
  59. 	}
  60.  
  61. 	void update(int pos, int val) {
  62. 		for (; pos >= 0; pos = (pos & (pos + 1)) - 1) {
  63. 			maximize(ft[pos], val); 
  64. 		}
  65. 	}
  66.  
  67. 	int get(int pos) {
  68. 		int ans = -INF; 
  69. 		for (; pos < n; pos = pos | (pos + 1)) {
  70. 			maximize(ans, ft[pos]); 
  71. 		}
  72. 		return ans; 
  73. 	}
  74. }; 
  75.  
  76. bool check(int M) {
  77. 	//     sum[j + 1..i] <= M  
  78. 	// <=> pref[i] - pref[j] <= M 
  79. 	// <=> pref[j] >= pref[i] - M 
  80. 	vector<int> vals;   
  81. 	for (int i = 0; i <= n; i++) {
  82. 		vals.push_back(pref[i]);   
  83. 	}
  84. 	sort(vals.begin(), vals.end());  
  85. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());  
  86. 	int sz = vals.size();   
  87.  
  88. 	FenwickMin fenw_min(sz);
  89. 	FenwickMax fenw_max(sz);  
  90. 	for (int i = 0; i <= n; i++) {
  91. 		// for (int j = 0; j < i; j++) {
  92. 		// 	if (pref[j] >= pref[i] - M) {
  93. 		// 		minimize(f[i], f[j] + 1); 
  94. 		// 		maximize(g[i], g[j] + 1); 
  95. 		// 	}
  96. 		// }
  97. 		if (i == 0) {
  98. 			f[0] = g[0] = 0;  
  99. 		}
  100. 		else {
  101. 			// Giá trị nén của pref[j] nhỏ nhất >= pref[i] - M
  102. 			int u = lower_bound(vals.begin(), vals.end(), pref[i] - M) - vals.begin();   
  103. 			f[i] = fenw_min.get(u) + 1;   
  104. 			g[i] = fenw_max.get(u) + 1; 
  105. 		}
  106. 		// Giá trị nén của pref[i]
  107. 		int v = lower_bound(vals.begin(), vals.end(), pref[i]) - vals.begin();   
  108. 		fenw_min.update(v, f[i]); 
  109. 		fenw_max.update(v, g[i]); 
  110. 	}
  111. 	return (f[n] <= k && k <= g[n]); 
  112. }
  113.  
  114. int main() {
  115. 	ios::sync_with_stdio(false); 
  116. 	cin.tie(nullptr);  	
  117. 	cin >> n >> k;   
  118. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  119.  
  120. 	for (int i = 1; i <= n; i++) {
  121. 		pref[i] = pref[i - 1] + a[i]; 
  122. 	}
  123.  
  124. 	int l = -1e9, r = 1e9, ans = -1;  
  125. 	while (l <= r) {
  126. 		int mid = (l + r) >> 1;  
  127. 		if (check(mid)) {
  128. 			ans = mid;  
  129. 			r = mid - 1; 
  130. 		}
  131. 		else {
  132. 			l = mid + 1; 
  133. 		}
  134. 	}
  135.  
  136. 	cout << ans << '\n'; 
  137. }
  138.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
9 4
1
1
1
3
2
2
1
3
1
stdout
copy 
5
https://ideone.com/4x2NQK
language:
C++14 (gcc 8.3)
created:
36 days ago
visibility:
secret

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!