fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define  piii pair<pair<int,int>,int>
  3. #define pii pair<int,int>
  4. #define node pair<piii,long long>
  5. using namespace std;
  6.  
  7. int n, k;
  8. long long val;
  9.  
  10. struct Comp {
  11.     bool operator()(const node& a, const node& b) {
  12.         return a.second > b.second; 
  13.     }
  14. };
  15. void solve() {
  16.     cin >> n >> k;
  17.     vector<long long> arr(n);
  18.     vector<pii> check(n);
  19.     vector<bool> checked(n,false);
  20.     long long res = 0;
  21.     int cnt = n - 1;
  22.     for (int i = 0; i < n; ++i) {
  23.         cin >> arr[i];
  24.         res += arr[i];
  25.     }
  26.     priority_queue<node,vector<node>, Comp> pq;
  27.     sort(arr.begin(),arr.end());
  28.     for (int i = 0; i < n - 1; ++i) {
  29.         pq.push({{{i-1,i+1},i},arr[i+1]-arr[i]});
  30.         check[i].first = i - 1, check[i].second = i + 1;
  31.     }
  32.     while (cnt > k - 1) {
  33.         node a = pq.top();
  34.         pq.pop();
  35.         int index = a.first.second;
  36.         if (checked[index] || a.first.first.first != check[index].first || 
  37.             a.first.first.second != check[index].second) continue;
  38.         checked[index] = true;
  39.         cnt--;
  40.         res += a.second;
  41.         int left = check[index].first, right = check[index].second;
  42.         if (left != -1) {
  43.             check[left].second = right;
  44.             val = (left-check[left].first)*(arr[right]-arr[left]);
  45.             pq.push({{{check[left].first,check[left].second},left},val});
  46.         }
  47.         if (right != n - 1) {
  48.             check[right].first = left;
  49.             val = (right - check[right].first)*(arr[check[right].second] - arr[right]);
  50.             pq.push({{{check[right].first,check[right].second},right},val});
  51.         }
  52.     }
  53.     cout << res;
  54. }
  55. int main() {
  56.     ios_base::sync_with_stdio(0);
  57.     cin.tie(0);cout.tie(0);
  58.     solve();
  59.     return 0;
  60. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10 4
4 1 12 17 7 3 6 8 10 16
stdout
copy 
94
https://ideone.com/p5LlOU
language:
C++14 (gcc 8.3)
created:
4 hours 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!