Submission #633514

#	Time	Username	Problem	Language	Result	Execution time	Memory
633514		ngano_upat_na	Stove (JOI18_stove)	C++17	0 / 100	0 ms	212 KiB

stove

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

struct s {
    ll dif;
    ll l;
    ll r;
};    

bool comp(s a, s b) {
    if (a.dif == b.dif) {
        return a.l < b.l;
    }   
    return a.dif > b.dif;
}   

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<ll> v(n);
    for (auto &e:v) cin >> e;
    for (int i=0; i<n; i++) {
        v[i] -= (v[0] - 1);
    }   
    vector<s> vs;
    
    if (n == 1) {
        cout << 1;
        return 0;
    }   
    if (k == 1) {
        cout << v[n-1] + 1 - v[0];
        return 0;
    }   
    
    for (int i=0; i<n - 1; i++) {
        ll DIF = v[i+1] - v[i], L = i, R = i+1;
        vs.push_back({DIF,L,R});
    }   
    sort(vs.begin(),vs.end(),comp);
    
    vector<pair<ll,ll>> vp;
    for (int i=0; i<k-1; i++) {
        ll fi = vs[i].l, se = vs[i].r;
        vp.push_back({fi,se});
    }   
    sort(vp.begin(),vp.end());
    
    ll ans = 0;
    ll cur = 0;
    for (int i=0; i<k-1; i++) {
        ll rh = v[vp[i].first] + 1;
        ans += (rh - cur);
        cur = v[vp[i].second];
    }      
    ans += (v[n - 1] - cur);
    cout << ans;
    return 0;
}   

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