Submission #1311979

#TimeUsernameProblemLanguageResultExecution timeMemory
1311979dymeztkyStove (JOI18_stove)C++20
100 / 100
18 ms2372 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define hello ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ub(a,x) upper_bound(a.begin(), a.end(), x)
#define lb(a,x) lower_bound(a.begin(), a.end(), x)
#define rep(m, n, k) for(int m = n; m <= k; m++)
#define rev(m, n, k) for(int m = n; m >= k; m--)
#define mnel(a) min_element(a.begin(), a.end())
#define mxel(a) max_element(a.begin(), a.end())
#define iii tuple<int,int,int>
#define vvi vector<vector<int>>
#define unmap unordered_map
#define unset unordered_set
#define pii pair<int,int>
#define mii map<int,int>
#define sz size() 
#define pb push_back
#define fi first
#define se second
#define endl "\n"

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> t(n+1);
    rep(i,1,n) cin >> t[i];

    vector<int> gap;
    rep(i,1,n-1) {
        int x = t[i+1] - t[i] - 1;
        if(x > 0) gap.pb(x);
    }   
    sort(gap.begin(), gap.end());

    int seg = 1 + gap.sz;
    int need = max(seg - k, 0LL);

    int ans = n;
    rep(i,0,need-1) ans += gap[i];
    cout << ans;
}

int32_t main() {
    hello;

    int t = 1;
    while(t--) {
        solve();
        cout << endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...