Submission #1346496

#TimeUsernameProblemLanguageResultExecution timeMemory
1346496samuelandrianoo_Stove (JOI18_stove)C++20
100 / 100
58 ms9776 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
        ios_base::sync_with_stdio(false); cin.tie(NULL);

        ll n, k; cin >> n >> k;
        priority_queue<pair<ll, pair<ll, ll>>> pq;
        ll arr[n + 5];
        for (ll i = 1; i <= n; i++) cin >> arr[i];
        for (ll i = 2; i <= n; i++){
                pq.push({arr[i] - arr[i - 1], {i, i - 1}});
        }
        ll sisa = k - 1;
        set<pair<ll, ll>> st;
        while(sisa--){
                auto ptr = pq.top(); pq.pop();
                ll idx0 = ptr.second.second, idx1 = ptr.second.first;
                st.insert({idx0, idx1});
        }

        ll ans = 0, l = 1;
        for (ll i = 1; i <= n; i++){
                if (st.find({i, i + 1}) != st.end() || i == n){ //ada
                        ans += (arr[i] - arr[l]) + 1;
                        l = i + 1;
                }
        }

        cout << ans << endl;
}

/*
        
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...