fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4.  
  5. ll dp[2000008];
  6. ll a[2000008];
  7.  
  8. int main () {
  9.  
  10. 	ios_base::sync_with_stdio(false);
  11. 	cin.tie(0);
  12. 	cout.tie(0);
  13.  
  14. // #ifndef ONLINE_JUDGE
  15. // 	freopen("input.txt", "r", stdin);
  16. // 	freopen("output.txt", "w", stdout);
  17. // 	freopen("error.txt" , "w" , stderr);
  18. // #endif
  19.  
  20.  
  21. 	ll n, k;
  22. 	cin >> n >> k;
  23.  
  24. 	for (ll i = 0; i < n; i++) {
  25. 		cin >> a[i];
  26. 	}
  27.  
  28.  
  29. 	priority_queue<pair<ll, ll>> pq;
  30. 	for (ll i = 0; i < k; i++) {
  31. 		dp[i] = a[i];
  32. 		pq.push({a[i], i});
  33. 	}
  34.  
  35. 	ll size = ceil(n / (k * 1.0));
  36. 	for (ll i = 1; i < size; i++) {
  37. 		pair<ll, ll> p_max1 = pq.top();
  38. 		pq.pop();
  39. 		pair<ll, ll> p_max2 = pq.top();
  40. 		pq.pop();
  41.  
  42. 		pq = priority_queue<pair<ll, ll>>();
  43.  
  44. 		for (ll j = k * i; j < n && j < k * i + k; j++) {
  45.  
  46. 			if (j - p_max1.second != k) {
  47. 				// use max_1
  48. 				dp[j] = a[j] + p_max1.first;
  49. 			} else {
  50. 				// use max_2
  51. 				dp[j]  = a[j] + p_max2.first;
  52. 			}
  53.  
  54. 			pq.push({dp[j], j});
  55. 		}
  56. 	}
  57.  
  58. 	ll max_sum = INT_MIN;
  59. 	for (ll i = 0; i < n; i++) {
  60. 		max_sum = max(max_sum, dp[i]);
  61. 	}
  62.  
  63. 	cout << max(max_sum, 0ll) << "\n";
  64.  
  65. 	return 0;
  66. }
Runtime error #stdin #stdout 0.12s 50220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xm0Xo0
language:
C++14 (gcc 8.3)
created:
5 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!