Submission #589249

#	Time	Username	Problem	Language	Result	Execution time	Memory
589249		MohamedFaresNebili	Stove (JOI18_stove)	C++14	100 / 100	32 ms	7624 KiB

stove

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                using namespace std;

                using ll = long long;
                using ld = long double;
                using ii = pair<ll, ll>;
                using vi = vector<int>;

                #define ff first
                #define ss second
                #define pb push_back
                #define all(x) (x).begin(), (x).end()
                #define lb lower_bound
                #define int ll
                #define double ld

                const int MOD = 1000 * 1000 * 1000 + 7;
                const double EPS = 1e-9;

                int N, K, A[100001], par[100001];
                int lf[100001], rf[100001];
                int res, C; bool vis[100001];
                int findSet(int v) {
                    if(par[v] == v) return v;
                    return par[v] = findSet(par[v]);
                }
                void unionSet(int u, int v) {
                    u = findSet(u), v = findSet(v);
                    if(u == v) return;
                    if(lf[u] > lf[v]) swap(u, v);
                    par[v] = u; rf[u] = rf[v]; C--;
                }

                int32_t main() {
                    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                    cin >> N >> K; C = N;
                    for(int l = 0; l < N; l++) cin >> A[l];
                    for(int l = 0; l < N; l++)
                        par[l] = l, lf[l] = A[l], rf[l] = A[l];
                    vector<pair<int, pair<int, int>>> E;
                    for(int l = 1; l < N; l++) {
                        E.pb({A[l] - A[l - 1], {l, l - 1}});
                    }
                    sort(E.begin(), E.end());
                    reverse(E.begin(), E.end());
                    while(E.size() && C > K) {
                        pair<int, pair<int, int>> P = E.back();
                        int U = P.ss.ff, V = P.ss.ss;
                        unionSet(U, V); E.pop_back();
                    }
                    for(int l = 0; l < N; l++) {
                        int i = findSet(l);
                        if(vis[i]) continue;
                        res += (rf[i] - lf[i] + 1);
                        vis[i] = 1;
                    }
                    cout << res << "\n";
                    return 0;
                }

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