Submission #1297187

#TimeUsernameProblemLanguageResultExecution timeMemory
1297187mahmudisaliStove (JOI18_stove)C++20
100 / 100
14 ms1552 KiB

// Designed by Mahmud Isali
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;


using pii = pair<int,int>;
using dbl = double;

#define int long long
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fastio() ios::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define newl cout << endl
#define spl debug(string(100,'-'))

template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>using ordered_multiset = tree<pair<T,int>, null_type, less<pair<T,int>>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>int sz(const T& x) { return (int)x.size(); }
template<class T>int upper_index(const vector<T> &a, const T &x) {return (int)(upper_bound(all(a), x) - a.begin());}
template<class T>int lower_index(const vector<T> &a, const T &x) {return (int)(lower_bound(all(a), x) - a.begin());}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int  INF  = (int)4e18;
const int  MOD  = 998244353;
const int  MOD2 = 998244353;
const int  N = 1e6 + 5;
const dbl  EPS  = 1e-12;
void solve(){
    int n,k;
    cin >> n >> k;
    int need = n - k;
    vector<int> v;
    int sum = 0;
    int lst = -1;
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum++;
        if(lst == -1)   {lst = x;continue;}
        v.pb(x - lst - 1);
        lst = x;
    }
    sort(all(v));
    for(int i = 0; i < need; i++)
        sum += v[i];
    cout << sum;
}   
 



signed main() {
    fastio();
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Test Case: " << i << endl;
        solve();
    }
}
    
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...