fork(1) download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <climits>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <map>
  8. #include <queue>
  9. #include <set>
  10. #include <vector>
  11. using namespace std;
  12. #define pb push_back
  13. #define fst first
  14. #define snd second
  15. #define sz(a) int((a).size())
  16. typedef long long ll;
  17. typedef pair<int, int> pii;
  18. typedef pair<ll, ll> pll;
  19. typedef vector<int> vi;
  20. typedef vector<ll> vll;
  21. const int INF = 1000 * 1000 * 1000;
  22. const ll LLINF = 1ll << 53;
  23. template<class T> void relaxmax(T& r, T v) { r = max(r, v); }
  24. template<class T> void relaxmin(T& r, T v) { r = min(r, v); }
  25.  
  26. vector<int> solve_slow(int n, int k, const vector<int>& A) {
  27. 	vector<int> dp(n, INF);
  28. 	// A, n, k, - defined
  29. 	// dp - all initialized to INF
  30. 	dp[0] = A[0];
  31. 	for (auto i = 1; i < n; i++) {
  32. 		auto max = -INF;
  33. 		for (auto j = i; j >= 0 && j >= i-k+1; j--) {
  34. 			if (A[j] > max)
  35. 				max = A[j];
  36. 			auto sum = max + (j > 0 ? dp[j-1] : 0);
  37. 			if (sum < dp[i])
  38. 				dp[i] = sum;
  39. 		}
  40. 	}
  41. 	// answer: dp[n-1]
  42. 	return dp;
  43. }
  44.  
  45. vector<int> solve_fast(int n, int k, const vector<int>& A) {
  46. 	vector<int> dp(n + 1);
  47. 	vector<int> C(n + 1, -INF);
  48. 	vector<int> q(n + 1);
  49. 	vector<int> ne(n + 1, -INF);
  50. 	int qback = 0, qfront = 0;
  51. 	auto cmp = [&](const int& x, const int& y) {
  52. 		int vx = dp[x] + C[x], vy = dp[y] + C[y];
  53. 		return vx != vy ? vx < vy : x < y;
  54. 	};
  55. 	set<int, decltype(cmp)> s(cmp);
  56.  
  57. 	dp[0] = 0;
  58. 	s.insert(0);
  59. 	q[qfront++] = 0;
  60.  
  61. 	for (int i = 1; i <= n; ++i) {
  62. 		C[i] = A[i - 1];
  63. 		auto it_last = lower_bound(q.begin() + qback, q.begin() + qfront, i, [=](const int& x, const int& y) {
  64. 			return C[x] > C[y];
  65. 		});
  66.  
  67. 		for (auto it = it_last; it != q.begin() + qfront; ++it) {
  68. 			s.erase(*it);
  69. 			C[*it] = A[i - 1];
  70. 			ne[*it] = i;
  71. 			if (it == it_last) s.insert(*it);
  72. 		}
  73.  
  74. 		dp[i] = dp[*s.begin()] + C[*s.begin()];
  75.  
  76. 		while (qback < qfront && dp[q[qfront]] >= dp[i]) {
  77. 			s.erase(q[qfront]);
  78. 			qfront--;
  79. 		}
  80.  
  81. 		q[qfront++] = i;
  82. 		C[i] = -INF;
  83. 		s.insert(i);
  84.  
  85. 		if (q[qback] == i - k) {
  86. 			s.erase(i - k);
  87.  
  88. 			if (qback + 1 != qfront && ne[q[qback]] > q[qback + 1]) {
  89. 				s.erase(q[qback + 1]);
  90. 				relaxmax(C[q[qback + 1]], C[i - k]);
  91. 				s.insert(q[qback + 1]);
  92. 			}
  93.  
  94. 			qback++;
  95. 		}
  96. 	}
  97.  
  98. 	return vector<int>(dp.begin() + 1, dp.end());
  99. }
  100.  
  101. int main() {
  102. 	srand(time(NULL));
  103. 	for (int t = 0; t < 100; ++t) {
  104. 		int n = rand() % 1000 + 1;
  105. 		int k = rand() % n + 1;
  106. 		vector<int> A(n);
  107. 		for (int i = 0; i < n; ++i) {
  108. 			A[i] = rand() % 10000;
  109. 		}			
  110. 		vector<int> v1 = solve_slow(n, k, A);
  111. 		vector<int> v2 = solve_fast(n, k, A);
  112. 		for (int i = 0; i < n; ++i)
  113. 			if (v1[i] != v2[i]) {
  114. 				puts("INPUT");
  115. 				printf("%d %d\n", n, k);
  116. 				for (int i = 0; i < n; ++i)
  117. 					printf("%d ", A[i]);
  118. 				puts("");
  119. 				puts("OUTPUT");
  120. 				for (int i = 0; i < n; ++i) printf("%d ", v1[i]);
  121. 				puts("");
  122. 				for (int i = 0; i < n; ++i) printf("%d ", v2[i]);
  123. 				puts("");
  124. 				puts("error");
  125. 				return 0;
  126. 			}
  127. 	}
  128. 	puts("good");
  129. 	return 0;
  130. }
  131.  
Success #stdin #stdout 0.09s 3472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
good
https://ideone.com/pIrsmo
language:
C++14 (gcc 8.3)
created:
7 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!