Submission #1147679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147679		kvintsekstakord	Stove (JOI18_stove)	C++20	100 / 100	60 ms	7344 KiB

stove

#include <bits/stdc++.h>
#define int int64_t

using namespace std;

int32_t main(){

    int n, k; cin >> n >> k;

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

    sort(a.begin(), a.end());

    vector<pair<int, int>> dist;
    dist.reserve(n);
    for(int i = 1; i < n; i++){
        dist.push_back({a[i]-a[i-1], i-1});
    }
    sort(dist.begin(), dist.end(), greater<pair<int, int>>());

    set<int> cutoff;
    for(int i = 0; i < k-1; i++){ 
        //cout << dist[i].first << ":" << dist[i].second << '\n';    
        cutoff.insert(dist[i].second);
    }

    int ans = 0;
    int curr = a[0];
    for(int i = 0; i < n; i++){
        if(cutoff.count(i) || i==n-1){
            ans+=a[i]+1-curr;
            if(i!=n-1) curr=a[i+1];
        }
    }
    cout << ans;
    

    return 0;
}

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