Submission #1323928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323928		rainerevan_	Stove (JOI18_stove)	C++20	100 / 100	19 ms	4020 KiB

stove

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 5;
const ll LOG = 30;
#define vll vector <ll>
#define pll pair <ll, ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " " << (x) << endl;

ll n, m;
ll a [MAXN];
ll par [MAXN];

ll bpk(ll x){
    if(par[x] == x) return x;
    return par[x] = bpk(par[x]);
}
void mrg(ll x, ll y){
    par[bpk(y)] = bpk(x);
}

void solve(){
    cin >> n >> m;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
        par[i] = i;
    }
    vector <pll> v;
    for(ll i = 1; i < n; i++){
        v.push_back({(a[i+1]-a[i]), i});
    }
    sort(v.begin(), v.end());
    for(ll i = 0; i < n-m; i++){
        mrg(v[i].se, v[i].se+1);
    }
    ll ans = 0;
    ll las = 0;
    for(ll i = 1; i <= n; i++){
        if(bpk(i) == i){
            if(las) ans += a[i-1] + 1 - a[las];
            las = i;
        }
    }
    ans += a[n] + 1 - a[las];
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // ll t; cin >> t;
    // while(t--) solve();
    solve();
}

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