Submission #1359854

#TimeUsernameProblemLanguageResultExecution timeMemory
1359854haykadamStove (JOI18_stove)C++20
100 / 100
11 ms2372 KiB
// ....   ....       ...      ..     ..  ...   ..
// ....   ....      .. ..      ..   ..   ... ..
// ...........     ..   ..       ...     .....
// ...........    .........      ...     .....
// ....   ....   ..       ..     ...     ... ..
// ....   ....  ..         ..    ...     ...   ..

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>
#include <stack>
#include <map>
#include <queue>
#include <cstring>
#include <string>
#include <tuple>
#include <utility>
#define ll long long
#define endl "\n"
#define ld long double 
#define db double
#define rt return 0
#define FAST ios::sync_with_stdio(false);cin.tie(nullptr)
#define pb push_back
#define lb lower_bound 
#define ub upper_bound 
#define V vector 
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define D2 vector<vector<int>>
#define pq priority_queue
#define frop freopen("676776","r",stdin);freopen("676776","w",stdout);
#define itn int 
#define tin int 
#define pss pair<string,string>
#define all(x) x.begin(),x.end()
using namespace std;
ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
const int ans = 1e9 + 7;
int main() {
    FAST;
    int n, k;
    cin >> n >> k;
    vector<ll>a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ll ans = a[n - 1] - a[0] + 1;
    vector<ll>tarb;
    for (int i = 1; i < n; i++) {
        tarb.pb(a[i] - a[i - 1] - 1);
    }
    sort(tarb.rbegin(), tarb.rend());
    for (int i = 0; i < min(k - 1, (int)tarb.size()); i++) {
        ans -= tarb[i];
    }
    cout << ans << endl;
    rt;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...