Submission #587025

#	Time	Username	Problem	Language	Result	Execution time	Memory
587025		snasibov05	Stove (JOI18_stove)	C++14	100 / 100	61 ms	1708 KiB

stove

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, k; cin >> n >> k;
    vector<int> t(n);
    for (int i = 0; i < n; ++i) cin >> t[i];

    vector<bool> stop(n); stop[n-1] = true;
    vector<pair<int, int>> dif(n-1);
    for (int i = 0; i < n-1; ++i) dif[i] = {t[i+1] - t[i], i};
    sort(dif.rbegin(), dif.rend());

    for (int i = 0; i < k-1; ++i) stop[dif[i].second] = true;

    int prev = t[0];
    int ans = 0;
    for (int i = 0; i < n; ++i){
        if (!stop[i]) continue;
        ans += t[i] - prev + 1;
        if (i != n-1) prev = t[i+1];
    }

    cout << ans << "\n";

    return 0;
}

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