Submission #1083902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083902		May27_th	Stove (JOI18_stove)	C++17	100 / 100	24 ms	2808 KiB

stove

#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

void Solve(void) {
  int N, K; cin >> N >> K;
  vector<int> T(N + 1);
  vector<bool> en(N + 1, false);
  vector<pair<int, int>> d;
  for (int i = 1; i <= N; i ++) {
    cin >> T[i];
    if (i > 1) {
      d.pb(mp(T[i] - T[i - 1], i - 1));
    }
  }
  sort(d.rbegin(), d.rend());
  for (int i = 0; i < K - 1; i ++) {
    en[d[i].second] = true;
    // cout << d[i].second << "\n";
  }
  int prev = -1;
  i64 ans = 0;
  for (int i = 1; i <= N; i ++) {
    if (prev == -1) prev = T[i];
    if (en[i]) {
      ans += T[i] + 1 - prev;
      prev = -1;
    }
  }
  if (prev != -1) ans += T[N] + 1 - prev;
  cout << ans << "\n";
}
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int Tests = 1; // cin >> Tests; 
  while (Tests --) {
    Solve();    
  }
}

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