Submission #1219603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219603		zxzuam	Stove (JOI18_stove)	C++20	100 / 100	12 ms	1864 KiB

stove

#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();
    }
} 

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