Submission #1219603

#TimeUsernameProblemLanguageResultExecution timeMemory
1219603zxzuamStove (JOI18_stove)C++20
100 / 100
12 ms1864 KiB
#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
#define vecint vector <int>
#define double long double
const int mod = 1e9 + 7;
const int N = 2e5 + 7;
const long long inf = 1e18;
const int NN = 107;
using namespace std;
/*vecint t(N * 4), a(N);
void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}
void update(int v, int tl, int tr, int pos, int x) {
    if (pos > tr || pos < tl) {
        return;
    }
    if (tl == tr) {
        t[v] = x;
        return;
    }
    int tm = (tl + tr) / 2;
    update(v * 2, tl, tm, pos, x);
    update(v * 2 + 1, tm + 1, tr, pos, x);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) {
        return inf;
    }
    if (l <= tl && tr <= r) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return min(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}*/
void solve() {
    int n, k;
    cin >> n >> k;
    k--;
    vecint a(n + 1);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = a[n] - a[1] + 1;
    vecint b(n);
    for(int i = 1; i < n; i++) {
        b[i] = a[i + 1] - a[i] - 1;
    }
    sort(b.begin() + 1, b.end());
    reverse(b.begin() + 1, b.end());
    for(int i = 1; i <= k; i++) {
        ans -= b[i];
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;
    while (tt--){
        solve();
    }
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...