Submission #717186

#	Time	Username	Problem	Language	Result	Execution time	Memory
717186		TimDee	Stove (JOI18_stove)	C++17	100 / 100	26 ms	9272 KiB

stove

//      ^                          ^ 
//      \\      ^ ^      ^ ^      //
//       \\___>(O.O)<  >(O_O)<___//
//       /  __ __ /      \ __ __  \
//      //// // //        \\ \\ \\\\

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

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,popcnt")

using ll = long long;
#define int long long
//#define double long double
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 1e9+7;//998244353;

const int N=1e5;

struct DSU {
    vector<int> p,r;
    DSU(int n) {
        forn(i,n) p.pb(i);
        forn(i,n) r.pb(0);
    }
    int get(int u) {
        return (p[u]==u)?u:get(p[u]);
    }
    void uni(int u, int v) {
        u=get(u), v=get(v);
        if (u==v) return;
        if (r[u]==r[v]) ++r[u];
        if (r[u]<r[v]) swap(u,v);
        p[v]=u;
    }
};
DSU dsu(N);
int ans[N];
set<int> stl[N];

void solve() {
    
    int n,k; cin>>n>>k;
    vector<int> a(n);
    for (int i=0; i<n; ++i) cin>>a[i];

    vector<int> b(n-1);
    for (int i=0; i<n-1; ++i) b[i]=a[i+1]-a[i]-1;

    sort(b.begin(), b.end());
    //acum b e sortat, adica b[i]<=b[i+1] pt orice i

                        //(sau ce era in problema)
    int ans = n; //pentru ca comp va lucra cel putin fiecare moment a[i];

    //acum avem n-1 intervale intre a[i] si a[i+1];
    //cand orim comp, 
    //noi il oprim imediat dupa un anumit a[i]
    //si il pornim la urmator a[i+1]
    //adica vrem sa alegem K CEI MAI MARI intervali
    //<=> adica adaugam la raspuns n-k cei mici
    //fii atenta ca inca odata trebuie sa l oprim dupa n-lea eveniment
    for (int i=0; i<n-k; ++i) ans+=b[i];

    cout<<ans;

}
     
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

stove.cpp:4:1: warning: multi-line comment [-Wcomment]
    4 | //       /  __ __ /      \ __ __  \
      | ^

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