fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long int
  3. using namespace std;
  4.  
  5. int main () {
  6.  
  7. 	ll n,k;
  8. 	cin>>n>>k;
  9.  
  10. 	ll a[n+1];
  11. 	for(ll i=0;i<n;i++){
  12. 		cin>>a[i];
  13. 	}
  14.  
  15. 	ll dp[n+1]={0};
  16. 	priority_queue<pair<ll,ll>> pq;
  17. 	for(ll i=0;i<k;i++){
  18. 		dp[i] = a[i];
  19. 		pq.push({a[i],i});
  20. 	}
  21.  
  22. 	ll size = ceil(n/(k*1.0));
  23. 	for(ll i=1;i<size;i++){
  24. 		pair<ll,ll> p_max1 = pq.top();
  25. 		pq.pop();
  26. 		pair<ll,ll> p_max2 = pq.top();
  27. 		pq.pop();
  28.  
  29. 		pq = priority_queue<pair<ll,ll>>();
  30.  
  31. 		for(ll j=k*i;j<n && j<k*i+k;j++){
  32.  
  33. 			if(j-p_max1.second != k){
  34. 				// use max_1
  35. 				dp[j] = a[j] + p_max1.first;
  36. 			}else{
  37. 				// use max_2
  38. 				dp[j]  = a[j] + p_max2.first;
  39. 			}	
  40.  
  41. 			pq.push({dp[j],j});
  42. 		}
  43. 	}
  44.  
  45. 	ll max_sum = INT_MIN;
  46. 	for(ll i=0;i<n;i++){
  47. 		max_sum = max(max_sum,dp[i]);
  48. 	}
  49.  
  50. 	cout<<max(max_sum,0ll)<<"\n";
  51.  
  52. 	return 0;
  53. }
Runtime error #stdin #stdout 0s 5836KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/MO1YxH
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!