제출 #1333580

#제출 시각아이디문제언어결과실행 시간메모리
1333580zhehanStove (JOI18_stove)C++20
100 / 100
56 ms3476 KiB
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;

#define int long long

signed main() {
  int n, k;
  cin >> n >> k;
  vector<int> t(n, 0);
  priority_queue<ii> diff;
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
    if (i > 0) {
      diff.push(ii(t[i] - t[i - 1], i - 1));
    }
  }
  priority_queue<int, vector<int>, greater<int>> splits;
  for (int i = 0; i < k - 1; ++i) {
    splits.push(diff.top().second);
    //cout << diff.top().second << '\n';
    diff.pop();
  }
  int sum = 0;
  int prev_ind = 0;
  while (!splits.empty()) {
    int i = splits.top();
    splits.pop();
    sum += t[i] + 1 - t[prev_ind];
    prev_ind = i + 1;
  }
  sum += t[n - 1] + 1 - t[prev_ind];
  cout << sum << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...