Submission #965580

#	Time	Username	Problem	Language	Result	Execution time	Memory
965580		vjudge1	Stove (JOI18_stove)	C++17	100 / 100	23 ms	6716 KiB

stove

#include <bits/stdc++.h>
using namespace std;
#define int     long long
#define ll      long long
#define pii     pair <int, int> 
#define pb      push_back
#define mp      make_pair
#define dbg     puts("dbg");
#define outp(x) cout << #x << " = " << (x) << endl
#define all(x)  (x).begin(), (x).end()
#define test    int t; cin >> t; while(t--){solve();}
#define MOD     998244353
int fpb(int a,int b){if(b == 0){return a;}return fpb(b, a%b);}
int kpk(int a,int b){return (a*b)/fpb(a, b);}

int n, k, t[100003], totGroupNow, par[100003];
vector <pair <int, pii>> v;

int root(int x){
    if(par[x] == x){
        return x;
    }
    par[x] = root(par[x]);
    return par[x];
}

void join(int x, int y){
    par[root(x)] = root(y);
}

bool cek(int x, int y){
    return (root(x) == root(y));
}

void solve(){   
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> t[i];
    }
    for(int i=2; i<=n; i++){
        v.pb({t[i]-t[i-1], {i-1, i}});
    }
    sort(all(v));
    totGroupNow = n;
    for(int i=1; i<=n; i++){
        par[i] = i;
    }
    for(auto i : v){
        if(totGroupNow == k) break;
        join(i.second.first, i.second.second);
        totGroupNow--;
    }
    int mini = t[1], maxi = t[1], res = 0;
    for(int i=2; i<=n+1; i++){
        if(cek(i-1, i)){
            maxi = t[i];
        } else {
            res += maxi - mini + 1;
            mini = t[i], maxi = t[i];
        }
        // cout << mini << " " << maxi << endl;
    }
    cout << res << endl;
}


int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

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