fork download
copy 
  1. /*input
  2. 3 6
  3. 1 3 4
  4. */
  5. #include <bits/stdc++.h>
  6. #include<stdio.h>
  7. using namespace std;
  8. #define pi pair<long long,long long>
  9. #define pii pair <ll,pi>
  10. #define F(i,a,b) for(ll i = (ll)(a); i <= (ll)(b); i++)
  11. #define RF(i,a,b) for(ll i = (ll)(a); i >= (ll)(b); i--)
  12. #define PI 3.14159265
  13. #define ll long long
  14. #define ff first
  15. #define ss second
  16. #define pb(x) push_back(x)
  17. #define mp(x,y) make_pair(x,y)
  18. #define debug(x) cout << #x << " = " << x << endl
  19. #define INF 1000000009
  20. #define mod 1000000007
  21. priority_queue < pii, vector<pii> > pq;
  22. map <pi,ll> mymap;
  23. ll a[500005],sum[500005]={0};
  24. int main() 
  25. {
  26. 	std::ios::sync_with_stdio(false);
  27. 	mymap.clear();
  28. 	while(!pq.empty())
  29. 		pq.pop();
  30. 	ll n,k;
  31. 	cin>>n>>k;
  32. 	F(i,1,n)
  33. 	{
  34. 		cin>>a[i];
  35. 		sum[i] += sum[i-1]+a[i];
  36. 	}
  37. 	pq.push(mp(sum[n],mp(1,n)));
  38. 	while(k--)
  39. 	{
  40. 		ll val = pq.top().ff;
  41. 		cout<<val<<" ";
  42. 		ll l = pq.top().ss.ff;
  43. 		ll r = pq.top().ss.ss;
  44. 		//cout<<l<<" "<<r<<" ";
  45. 		pq.pop();
  46. 		mymap[mp(l,r)] = 1;
  47. 		if(l!=r)
  48. 		{
  49. 			val = sum[r]-sum[l];
  50. 			if(!mymap[mp(l+1,r)])
  51. 			{
  52. 				pq.push(mp(val,mp(l+1,r)));
  53. 				//cout<<l+1<<" "<<r<<" ";
  54. 				mymap[mp(l+1,r)]=1;
  55. 			}
  56. 			val = sum[r-1]-sum[l-1];
  57. 			if(!mymap[mp(l,r-1)])
  58. 			{
  59. 				pq.push(mp(val,mp(l,r-1)));
  60. 				mymap[mp(l,r-1)]=1;
  61. 				//cout<<l<<" "<<r-1<<endl;
  62. 			}
  63. 		}
  64. 		//cout<<endl;
  65. 	}
  66. 	return 0;
  67. }
Runtime error #stdin #stdout 0.01s 11224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tPfXgC
language:
C++14 (gcc 8.3)
created:
8 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!