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