Submission #650672

#	Time	Username	Problem	Language	Result	Execution time	Memory
650672		Shin	Stove (JOI18_stove)	C++14	100 / 100	20 ms	2384 KiB

stove

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, k; cin >> n >> k;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i ++) {
    cin >> a[i];
  }
  vector<int> gap;
  long long res = a[n] - a[1] + 1;
  for (int i = 2; i <= n; i ++) {
    gap.push_back(a[i] - a[i - 1] - 1);
  }
  sort(gap.begin(), gap.end());
  reverse(gap.begin(), gap.end());
  k --;
  for (int x: gap) {
    if ((-- k) < 0) {
      break;
    }
    res -= x;
  }
  cout << res;
  return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50