Submission #1242317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242317		vanhpp	Stove (JOI18_stove)	C++20	100 / 100	44 ms	5176 KiB

stove

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pq priority_queue
using namespace std;

const ll MAXN = 100005;
ll n, k;
vector<pair<ll, ll>> pa;
vector<pair<ll, ll>> nw;

vector<pair<ll, ll>> inter() {
    nw.clear();
    nw.push_back(pa[0]);
    for (int i = 1; i < n; i++) {
        ll st = pa[i].fi;
        ll ed = pa[i].se;
        ll& led = nw.back().se;
        if (st <= led) {
            led = max(led, ed);
        } else {
            nw.push_back({st, ed});
        }
    }
    return nw;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        ll x;
        cin >> x;
        pa.push_back({x, x + 1});
    }
    sort(pa.begin(), pa.end());
    inter();

    ll m = nw.size();
    ll tong = 0;
    for (auto x : nw) {
        tong += x.se - x.fi;
    }

    if (m <= k) {
        cout << tong;
        return 0;
    }

    vector<ll> gap;
    for (int i = 1; i < m; i++) {
        gap.push_back(nw[i].fi - nw[i - 1].se);
    }
    sort(gap.begin(), gap.end());
    for (int i = 0; i < m - k; i++) {
        tong += gap[i];
    }
    cout << tong;
    return 0;
}

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