fork download 
  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 maximize(T& a, const T& b) {
  12. 	if (b < a) return false; 
  13. 	a = b; 
  14. 	return true; 
  15. }
  16.  
  17. const int N = 1e5 + 5; 
  18.  
  19. int n, k; 
  20. int a[N]; 
  21.  
  22. ll seg[4 * N];  
  23.  
  24. void update(int id, int l, int r, int pos, ll val) {
  25. 	if (l > pos || r < pos) return;  
  26.  
  27. 	maximize(seg[id], val);   
  28. 	if (l == r) return;  
  29.  
  30. 	int mid = (l + r) >> 1; 
  31. 	update(id * 2, l, mid, pos, val); 
  32. 	update(id * 2 + 1, mid + 1, r, pos, val); 
  33. }
  34.  
  35. ll getMax(int id, int l, int r, int u, int v) {
  36. 	if (l > v || r < u) return -LINF; 
  37.  
  38. 	if (u <= l && r <= v) return seg[id];  
  39.  
  40. 	int mid = (l + r) >> 1; 
  41. 	return max(getMax(id * 2, l, mid, u, v), getMax(id * 2 + 1, mid + 1, r, u, v)); 
  42. }
  43.  
  44. ll dp[N]; // dp[i] = Số tiền nhiều nhất kiếm được nếu bắt đầu chọn từ hộp thứ i 
  45.  
  46. int main() {
  47. 	ios::sync_with_stdio(0); cin.tie(0);  	
  48. 	cin >> n >> k; 
  49. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  50.  
  51. 	// for (int i = n; i >= 1; i--) {
  52. 	// 	dp[i] = a[i];  
  53. 	// 	for (int j = i + 1; j <= min(n, i + k); j++) {
  54. 	// 		maximize(dp[i], a[i] + dp[j]); 
  55. 	// 	} 
  56. 	// }
  57.  
  58. 	for (int i = n; i >= 1; i--) {
  59. 		// chỉ chọn duy nhất hộp i 
  60. 		dp[i] = a[i];  
  61.  
  62. 		// chọn hộp i cùng một số hộp khác ở phía sau
  63. 		maximize(dp[i], a[i] + getMax(1, 1, n, i + 1, min(n, i + k))); 
  64.  
  65. 		update(1, 1, n, i, dp[i]); 
  66. 	}
  67.  
  68. 	ll ans = 0;   
  69. 	for (int i = 1; i <= n; i++) maximize(ans, dp[i]); 
  70.  
  71. 	cout << ans << '\n'; 
  72. }
  73.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
5 2
-1 -2 3 -4 5
stdout 
8
https://ideone.com/OVGjhc
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!