fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5.  
  6. struct compare  
  7. {  
  8.  bool operator()(const int& l, const int& r)  
  9.  {  
  10.    return l > r;  
  11.  }  
  12. }; 
  13. int main()
  14. {
  15.   int n, k;
  16.   cin >> n >> k;
  17.   int arr[250000]={0x00,};
  18.   for(int i = 0; i<n; i++)
  19.   {
  20.     cin >> arr[i];
  21.   }
  22.   long sum = 0;
  23.   for(int i = 0; i<=n-k; i++)
  24.   {
  25.     priority_queue<int> max_heap;
  26.     priority_queue<int,vector<int>, compare> min_heap;
  27.     for(int j = i; j<i+k; j++)
  28.     {
  29.       max_heap.push(arr[j]);
  30.       if(max_heap.size()-min_heap.size() > 1)
  31.       {
  32.         int data =max_heap.top();
  33.         max_heap.pop();
  34.         min_heap.push(data);
  35.       } 
  36.     }
  37.     int median = max_heap.top() < min_heap.top() ? max_heap.top() : min_heap.top();
  38.     sum += median;
  39.   }
  40.   cout << sum<<endl;
  41.   return 0;
  42. }
Success #stdin #stdout 0s 16912KB
comments (?)
stdin
copy 
10 3
3 4 5 6 7 8 9 10 11 12
stdout
copy 
60
https://ideone.com/RUdvK9
language:
C++ (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!