oj.uz

Submission #717186

# Submission time Handle Problem Language Result Execution time Memory
717186 2023-04-01T11:18:41 Z TimDee Stove (JOI18_stove) C++17
100 / 100
 26 ms 9272 KB 
//      ^                          ^ 
//      \\      ^ ^      ^ ^      //
//       \\___>(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

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 5 ms 6620 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 4 ms 6604 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 4 ms 6672 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 5 ms 6620 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 4 ms 6604 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 4 ms 6672 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct
10 Correct 5 ms 6780 KB Output is correct
11 Correct 5 ms 6732 KB Output is correct
12 Correct 7 ms 6732 KB Output is correct
13 Correct 5 ms 6780 KB Output is correct
14 Correct 6 ms 6732 KB Output is correct
15 Correct 6 ms 6732 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 5 ms 6620 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 4 ms 6604 KB Output is correct
5 Correct 4 ms 6604 KB Output is correct
6 Correct 4 ms 6672 KB Output is correct
7 Correct 5 ms 6604 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct
10 Correct 5 ms 6780 KB Output is correct
11 Correct 5 ms 6732 KB Output is correct
12 Correct 7 ms 6732 KB Output is correct
13 Correct 5 ms 6780 KB Output is correct
14 Correct 6 ms 6732 KB Output is correct
15 Correct 6 ms 6732 KB Output is correct
16 Correct 22 ms 9160 KB Output is correct
17 Correct 22 ms 9272 KB Output is correct
18 Correct 21 ms 9148 KB Output is correct
19 Correct 23 ms 9152 KB Output is correct
20 Correct 22 ms 9236 KB Output is correct
21 Correct 22 ms 9152 KB Output is correct
22 Correct 26 ms 9164 KB Output is correct
23 Correct 22 ms 9240 KB Output is correct
24 Correct 22 ms 9160 KB Output is correct