fork download
copy 
  1. #include <iostream>
  2. #include <set>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int main() {
  8.  
  9. 	long long n,k;
  10. 	cin>>n>>k;
  11.  
  12. 	long long a[n];
  13. 	for(long long i=0;i<n;i++)
  14. 	{
  15. 		cin>>a[i];
  16. 	}
  17.  
  18. 	if(k == 1)
  19. 	{
  20. 		for(long long i=0;i<n;i++)
  21. 		{
  22. 			cout<<0<<" ";
  23. 		}
  24. 		return 0;
  25. 	}
  26.  
  27. 	vector<long long> V;
  28. 	long long sum=0;
  29. 	for(long long i=0;i<k;i++)
  30. 	{
  31. 		V.push_back(a[i]);
  32. 		sum+=a[i];
  33. 	}
  34.  
  35. 	sort(V.begin(),V.end());
  36. 	multiset<long long> LS;
  37. 	multiset<long long> RS;
  38. 	long long sum1 =0;
  39. 	long long sum2=0;
  40. 	if(k%2 == 0)
  41. 	{
  42. 		for(long long i=0;i<V.size()/2;i++)
  43. 		{
  44. 			LS.insert(V[i]);
  45. 			sum1+=V[i];
  46. 		}
  47.  
  48. 		for(long long i=V.size()/2;i<V.size();i++)
  49. 		{
  50. 			RS.insert(V[i]);
  51. 			sum2+=V[i];
  52. 		}
  53. 		long long median = *LS.rbegin();
  54. 		long long cost=0;
  55. 		cost+=median*LS.size() - sum1;
  56. 		cost+=sum2-median*RS.size();
  57. 		cout<<cost<<" ";
  58. 		for(long long i=k;i<n;i++)
  59. 		{
  60. 			if(LS.find(a[i-k]) != LS.end())
  61. 			{
  62. 				LS.erase(LS.find(a[i-k]));
  63. 				sum1 -= a[i-k];
  64. 				LS.insert(*RS.begin());
  65. 				sum1 += *RS.begin();
  66. 				sum2-= *RS.begin();
  67. 				RS.erase(RS.begin());
  68.  
  69. 			}
  70. 			else if(RS.find(a[i-k]) != RS.end())
  71. 			{
  72. 				RS.erase(RS.find(a[i-k]));
  73. 				sum2 -= a[i-k];
  74. 			}
  75.  
  76. 			if(LS.size() > 0 && a[i] >= *(LS.rbegin()))
  77. 			{
  78. 				RS.insert(a[i]);
  79. 				sum2+=a[i];
  80. 			}
  81. 			else
  82. 			{
  83. 				LS.insert(a[i]);
  84. 				sum1+=a[i];
  85. 			}
  86.  
  87. 			if(LS.size() < RS.size())
  88. 			{
  89. 				LS.insert(*(RS.begin()));
  90. 				sum1+=*RS.begin();
  91. 				sum2-=*RS.begin();
  92. 				RS.erase(RS.begin());
  93. 			}
  94. 			else if(LS.size() > RS.size())
  95. 			{
  96. 				while((LS.size() - RS.size()) > 0)
  97. 				{
  98. 					RS.insert(*(LS.rbegin()));
  99. 					sum2+=*(LS.rbegin());
  100. 					sum1-=*(LS.rbegin());
  101. 					LS.erase(--LS.end());
  102. 				}
  103. 			}
  104.  
  105. 			//cout<<"LS.size()="<<LS.size()<<" RS.size()="<<RS.size()<<endl;
  106. 			median=*LS.rbegin();
  107. 			cost=0;
  108. 			cost+=median*LS.size() - sum1;
  109. 			cost+=sum2-median*RS.size();
  110. 			cout<<cost<<" ";
  111. 		}
  112. 	}
  113. 	else 
  114. 	{
  115. 		for(long long i=0;i<V.size()/2+1;i++)
  116. 		{
  117. 			LS.insert(V[i]);
  118. 			sum1+=V[i];
  119. 		}
  120.  
  121. 		for(long long i=V.size()/2+1;i<V.size();i++)
  122. 		{
  123. 			RS.insert(V[i]);
  124. 			sum2+=V[i];
  125. 		}
  126.  
  127. 		long long median = *LS.rbegin();
  128. 		long long cost=0;
  129. 		cost+=median*LS.size() - sum1;
  130. 		cost+=sum2-median*RS.size();
  131. 		cout<<cost<<" ";
  132. 		for(long long i=k;i<n;i++)
  133. 		{
  134. 			if(LS.find(a[i-k]) != LS.end())
  135. 			{
  136. 				LS.erase(LS.find(a[i-k]));
  137. 				sum1-=a[i-k];
  138. 				LS.insert(*RS.begin());
  139. 				sum1+=*RS.begin();
  140. 				sum2-=*RS.begin();
  141. 				RS.erase(RS.begin());
  142.  
  143. 			}
  144. 			else if(RS.find(a[i-k]) != RS.end())
  145. 			{
  146. 				RS.erase(RS.find(a[i-k]));
  147. 				sum2 -= a[i-k];
  148. 			}
  149.  
  150. 			if(LS.size() > 0 && a[i] >= *(LS.rbegin()))
  151. 			{
  152. 				RS.insert(a[i]);
  153. 				sum2+=a[i];
  154. 			}
  155. 			else
  156. 			{
  157. 				LS.insert(a[i]);
  158. 				sum1+=a[i];
  159. 			}
  160.  
  161. 			if(LS.size() < RS.size())
  162. 			{
  163. 				LS.insert(*(RS.begin()));
  164. 				sum1+=*(RS.begin());
  165. 				sum2-=*(RS.begin());
  166. 				RS.erase(RS.begin());
  167. 			}
  168. 			else if(LS.size() > RS.size())
  169. 			{
  170. 				while((LS.size() - RS.size()) > 1)
  171. 				{
  172. 					RS.insert(*(LS.rbegin()));
  173. 					sum2+=*(LS.rbegin());
  174. 					sum1-=*(LS.rbegin());
  175. 					LS.erase(--LS.end());
  176. 				}
  177. 			}
  178.  
  179. 			//cout<<"LS.size()="<<LS.size()<<" RS.size()="<<RS.size()<<endl;
  180.  
  181. 			median = *LS.rbegin();
  182. 			cost=0;
  183. 			cost+=median*LS.size() - sum1;
  184. 			cost+=sum2-median*RS.size();
  185. 			cout<<cost<<" ";
  186. 		}
  187. 	}
  188.  
  189.  
  190. 	return 0;
  191. }
  192.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
8 3
2 4 3 5 8 1 2 1
stdout
copy 
2 2 5 7 7 1
https://ideone.com/LF4o4x
language:
C++14 (gcc 8.3)
created:
5 days 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!