Submission #896406

#	Time	Username	Problem	Language	Result	Execution time	Memory
896406		SuPythony	Stove (JOI18_stove)	C++17	100 / 100	45 ms	3280 KiB

stove

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k; cin>>n>>k;
    vector<int> t(n);
    vector<int> off(n,0);
    vector<pair<int,int>> diffs;
    for (int i=0; i<n; i++) {
        cin>>t[i];
        if (i>0) {
            diffs.push_back({t[i]-t[i-1]+1, i-1});
        }
    }
    sort(diffs.begin(), diffs.end(), greater<pair<int,int>>());
    for (int i=0; i<k-1; i++) {
        off[diffs[i].second]=1;
    }
    off[n-1]=1;
    int ind=0;
    long long ans=0;
    while (ind<n) {
        int start=ind;
        while (!off[ind]) {
            ind++;
        }
        ans+=(t[ind]-t[start]+1);
        ind++;
    }
    cout << ans;
    return 0;
}

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