Submission #996497

#	Time	Username	Problem	Language	Result	Execution time	Memory
996497		overwatch9	Stove (JOI18_stove)	C++17	100 / 100	46 ms	5328 KiB

stove

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
using ll = long long;
vector <int> t;
struct DSU {
    vector <int> link, sz;
    vector <ll> mn, mx;
    DSU (int s) {
        link = sz = vector <int> (s + 1);
        mx = mn = vector <ll> (s+1);
        for (int i = 1; i <= s; i++) {
            link[i] = i;
            sz[i] = 1;
            mx[i] = mn[i] = t[i];
        }
    }
    int head(int x) {
        while (x != link[x])
            x = link[x];
        return x;
    }
    bool same(int a, int b) {
        return head(a) == head(b);
    }
    void unite(int a, int b) {
        a = head(a);
        b = head(b);
        if (a == b)
            return;
        if (sz[a] < sz[b])
            swap(a, b);
        sz[a] += sz[b];
        link[b] = a;
        mx[a] = max(mx[a], mx[b]);
        mn[a] = min(mn[a], mn[b]);
    }
};
int main() {
    int n, k;
    cin >> n >> k;
    t = vector <int> (n+1);
    for (int i = 1; i <= n; i++)
        cin >> t[i];
    DSU dsu(n+1);
    priority_queue <pair <ll, pair <int, int>>> pq;
    for (int i = 1; i+1 <= n; i++) {
        pq.push({-t[i+1] + t[i], {i, i+1}});
    }
    int cnt = n;
    while (cnt > k) {
        int a = pq.top().second.first, b = pq.top().second.second;
        pq.pop();
        if (dsu.same(a, b)) 
            continue;
        dsu.unite(a, b);
        cnt--;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i == dsu.head(i)) {
            ans += dsu.mx[i] - dsu.mn[i] + 1;
        }
    }
    cout << ans << '\n';
}

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