Submission #823650

#	Time	Username	Problem	Language	Result	Execution time	Memory
823650		SoulKnight	Stove (JOI18_stove)	C++17	100 / 100	34 ms	4560 KiB

stove

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

#define ll long long
#define ln '\n'

const int N = 1e5 + 5;
const int LG = 20;
const int INF = 2e9 + 5;
const int MOD = 998244353;

ll a[N];
priority_queue<pair<ll, ll>> pq;
vector<int> vec;
ll ans = 0LL;

void solve(){
    int n, k; cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i < n; i++){
        pq.push({a[i] - a[i-1], i-1});
    }
    vec.push_back(-1);
    int t = k;
    while (--t && !pq.empty()){
        // cout << pq.top().first << ' ' << pq.top().second << ln;
        vec.push_back(pq.top().second);
        pq.pop();
    }
    sort(vec.begin(), vec.end());
    int x = vec.size();
    // for (int i = 0; i < x; i++) cout << vec[i] << ' ';
    // cout << ln;
    for (int i = 1; i < x; i++){
        // cout << a[vec[i]] << ' ' << a[vec[i-1]+1] << ln;
        ans += a[vec[i]]- a[vec[i-1]+1];
    }
    ans += a[n-1] - a[vec[x-1]+1];

    cout << ans + k << ln;





}



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

    // freopen("mooyomooyo.in", "r", stdin);
    // freopen("mooyomooyo.out", "w", stdout);


    // ll T; cin >> T;
    // while (T--){
    //     solve();
    // }


    solve();




    return 0;
}

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