oj.uz

Submission #1115397

# Submission time Handle Problem Language Result Execution time Memory
1115397 2024-11-20T12:24:38 Z staszic_ojuz Stove (JOI18_stove) C++17
100 / 100
 848 ms 128364 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

typedef long long ll;

struct triple {
    ll a;
    ll b;
    ll c;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, k; cin >> n >> k;
    vector<bool> os(1e9, false);
    ll pren = n;
    ll last = 0;
    for(int i = 0; i < n; i++) {
        ll t; cin >> t;
        os[t-1] = true;
        last = max(last, t);
    }

    vector<pair<ll,ll>> prze;
    if(os[0]) {
        prze.push_back({0, 1});
    }
    for(int i = 1; i < last + 1; i++) {
        if(os[i]) {
            if(os[i - 1]) {
                prze[prze.size() - 1].second+=1;
            } else {
                prze.push_back({i, 1});
            }
        }
    }
    n = prze.size();
    // ll st = n/k;
    // ll nad = n%k;
    
    vector<pair<ll, pair<ll,ll>>> diff(n - 1);
    for(int i = 0; i < n - 1; i++) {
        diff[i].first = prze[i + 1].first - prze[i].first - prze[i].second;
        diff[i].second = {i, i + 1};
        //cout << diff[i].first << " ";
    }

    sort(diff.begin(), diff.end(), [](pair<ll, pair<ll,ll>> a, pair<ll, pair<ll,ll>> b) {return a.first > b.first;});

    ll dod = prze.size() - k;
    ll wyn = pren;
    for(int i = 0; i < dod; i++) {
        wyn += diff[diff.size() - 1].first;
        diff.pop_back();
    }
    cout << wyn;


    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 122696 KB Output is correct
2 Correct 49 ms 122592 KB Output is correct
3 Correct 56 ms 122696 KB Output is correct
4 Correct 40 ms 122712 KB Output is correct
5 Correct 56 ms 122696 KB Output is correct
6 Correct 54 ms 122700 KB Output is correct
7 Correct 47 ms 122700 KB Output is correct
8 Correct 55 ms 122620 KB Output is correct
9 Correct 59 ms 122696 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 122696 KB Output is correct
2 Correct 49 ms 122592 KB Output is correct
3 Correct 56 ms 122696 KB Output is correct
4 Correct 40 ms 122712 KB Output is correct
5 Correct 56 ms 122696 KB Output is correct
6 Correct 54 ms 122700 KB Output is correct
7 Correct 47 ms 122700 KB Output is correct
8 Correct 55 ms 122620 KB Output is correct
9 Correct 59 ms 122696 KB Output is correct
10 Correct 770 ms 123100 KB Output is correct
11 Correct 804 ms 122880 KB Output is correct
12 Correct 774 ms 122740 KB Output is correct
13 Correct 785 ms 122952 KB Output is correct
14 Correct 783 ms 122856 KB Output is correct
15 Correct 777 ms 122952 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 122696 KB Output is correct
2 Correct 49 ms 122592 KB Output is correct
3 Correct 56 ms 122696 KB Output is correct
4 Correct 40 ms 122712 KB Output is correct
5 Correct 56 ms 122696 KB Output is correct
6 Correct 54 ms 122700 KB Output is correct
7 Correct 47 ms 122700 KB Output is correct
8 Correct 55 ms 122620 KB Output is correct
9 Correct 59 ms 122696 KB Output is correct
10 Correct 770 ms 123100 KB Output is correct
11 Correct 804 ms 122880 KB Output is correct
12 Correct 774 ms 122740 KB Output is correct
13 Correct 785 ms 122952 KB Output is correct
14 Correct 783 ms 122856 KB Output is correct
15 Correct 777 ms 122952 KB Output is correct
16 Correct 797 ms 128072 KB Output is correct
17 Correct 848 ms 127680 KB Output is correct
18 Correct 814 ms 127680 KB Output is correct
19 Correct 814 ms 128248 KB Output is correct
20 Correct 778 ms 127780 KB Output is correct
21 Correct 776 ms 128192 KB Output is correct
22 Correct 782 ms 128192 KB Output is correct
23 Correct 758 ms 128364 KB Output is correct
24 Correct 788 ms 127680 KB Output is correct