Submission #1332221

#TimeUsernameProblemLanguageResultExecution timeMemory
1332221eldarrStove (JOI18_stove)C++20
100 / 100
39 ms2336 KiB
#include <bits/stdc++.h>
#define ll long long
#define dl double
#define str string
#define tst to_string
#define pb push_back
#define pf push_front
#define eb emplace_back
#define u_b upper_bound
#define l_b lower_bound
#define ff first
#define ss second
#define INF 1000000001
#define mxn 100001
#define mod 998244353
#define come_on ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
struct modint {
    int x;
    modint(ll v = 0) { x = (v % mod + mod) % mod; }
    modint operator+(const modint &o) const { return modint(x + o.x); }
    modint operator-(const modint &o) const { return modint(x - o.x); }
    modint operator*(const modint &o) const { return modint(1LL * x * o.x % mod); }
};
modint modpow(modint a, ll e)
{
    modint res=1;
    while(e)
    {
        if(e&1) res=res*a;
        a=a*a;
        e>>=1;
    }
    return res;
}
modint inv(modint a){ return modpow(a, mod - 2);}
modint operator/(const modint &a, const modint &b) {
    return a*inv(b);
}
ostream &operator<<(ostream &os, const modint &m) {
    return os << m.x;
}

void solve()
{
    int n,k;
    cin>>n>>k;
    vector<ll>t(n);
    for(int i=0;i<n;i++)
    {
        cin>>t[i];
    }
    ll total=(t[n-1]+1)-t[0];
    vector<ll>v;
    for(int i=0;i<n-1;i++)
    {
        ll gap=t[i+1]-(t[i]+1);
        if(gap>0)
        {
            v.pb(gap);
        }
    }
    sort(v.rbegin(),v.rend());
    for(int i=0;i<k-1 && i<v.size();i++)
    {
        total-=v[i];
    }
    cout<<total<<'\n';
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...