Submission #378113

#	Time	Username	Problem	Language	Result	Execution time	Memory
378113		jlallas384	Stove (JOI18_stove)	C++17	100 / 100	79 ms	8672 KiB

stove

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

struct dsu{
    vector<int> sz,par;
    dsu(int n): sz(n,1),par(n){
        iota(par.begin(),par.end(),0);
    }
    int find(int a){
        return a == par[a] ? a : par[a] = find(par[a]);
    }
    void unite(int a,int b){
        a = find(a), b = find(b);
        if(sz[a] < sz[b]) swap(a,b);
        sz[a] += sz[b];
        par[b] = a;
    }
};

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    for(auto &x: a){
        cin >> x;
    }
    dsu d(n);
    vector<pair<int,int>> edges;
    for(int i = 0; i < n - 1; i++){
        edges.emplace_back(a[i+1] - a[i], i);
    }
    sort(edges.begin(), edges.end());
    vector<vector<int>> comp(n);
    for(int i = 0; i < n - k; i++){
        d.unite(edges[i].second,edges[i].second+1);
    }
    for(int i = 0; i < n; i++){
        comp[d.find(i)].push_back(a[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(comp[i].size() == 1) ans++;
        else if(comp[i].size() > 1) ans += comp[i].back() - comp[i][0] + 1;
    }
    cout << ans;
}

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