제출 #553828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553828		MadokaMagicaFan	Stove (JOI18_stove)	C++14	100 / 100	35 ms	3668 KiB

stove

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;

#define all(v)                      v.begin(), v.end()
#define rall(v)                     v.rbegin(), v.rend()
#define sz(v)                       ((int)v.size())

#define forn(i,n)                   for(int i = 0; i < n; ++i)
#define forbe(i,b,e)                for(int i = b; i < e; ++i)

#define pb                          push_back

#define pry                         puts("YES")
#define prn                         puts("NO")
#define endl                        '\n'

#define fst                         first
#define scn                         second

const int N = 1e5;

int p[N], s[N];

int getp(int x){
    return p[x] = (p[x] == x) ? x : getp(p[x]);
}

int uni(int a, int b){
    a = getp(a);
    b = getp(b);
    if (a == b) return 0;
    if (s[a] > s[b]) swap(a,b);
    p[a] = b;
    s[b] += s[a];
    return 1;
}

using ti = array<int,3>;

void solve(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; ++i){
        p[i] = i;
        s[i] = 1;
    }

    int x, y;
    cin >> x;

    priority_queue<ti, vector<ti>, greater<ti>> q;

    for(int i = 0; i < n-1; ++i){
        cin >> y;
        q.push({y-x,i,i+1});
        x = y;
    }

    int ans = 0;
    while(q.size() && n > k){
        auto u = q.top();
        q.pop();

        if (uni(u[2],u[1])){
            ans += u[0];
            --n;
        }
    }

    cout << ans + k << endl;
}

int32_t main(){
    #ifndef ONPC
        ios_base::sync_with_stdio(0);cin.tie(0);
    #else
        freopen("in", "r", stdin);
    #endif
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}

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