Submission #226067

#	Time	Username	Problem	Language	Result	Execution time	Memory
226067		dvdg6566	Stove (JOI18_stove)	C++14	100 / 100	77 ms	3312 KiB

stove

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 100100;
const ll INF = 1e18;
const ll MOD = 1e9+7;

ll A[MAXN];
ll ans;
vi V;
ll N,K,a,b;

int main(){
    cin>>N>>K;
    ans=N;
    for (int i=1;i<=N;++i)cin>>A[i];
    // for (int i=1;i<=N;++i)cout<<A[i]<<' ';cout<<'\n';
    for (int i=1;i<N;++i)V.pb(A[i+1]-A[i]-1);
    sort(ALL(V));reverse(ALL(V));
    // for (auto i:V)cout<<i<<'\n';
    --K;
    while (SZ(V)>K){ans+=V.back();V.pop_back();}
    cout<<ans;
}

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