Submission #931253

#	Time	Username	Problem	Language	Result	Execution time	Memory
931253		HaciyevAlik	Stove (JOI18_stove)	C++14	100 / 100	18 ms	4312 KiB

stove

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define oo 1000000000000
const ll mx=1e5+5;
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k,cnt=1,dif=oo; cin >> n >> k;
    vector<ll> t(n);
    vector<pair<ll,ll>> v;
    for(ll i=0;i<n;++i) {
        cin >> t[i];
    }
    for(ll i=1;i<n;++i) {
        if(t[i]==t[i-1]+1) {
            ++cnt;
        } else {
            v.push_back({dif,cnt});
            cnt=1;
            dif=t[i]-t[i-1]-1;
        }
    }
    v.push_back({dif,cnt});
    sort(v.rbegin(),v.rend());
    ll ans=0;
    for(ll i=0;i<min(k,ll(v.size()));++i) {
        ans += v[i].second;
    }
    for(ll i=k;i<ll(v.size());++i) {
        ans=ans+v[i].first+v[i].second;
    }
    cout << ans;
    return 0;
}

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