oj.uz

Submission #680974

# Submission time Handle Problem Language Result Execution time Memory
680974 2023-01-12T07:27:00 Z Alexandruabcde Stove (JOI18_stove) C++14
100 / 100
 44 ms 6388 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair <LL, int> PLLI;
constexpr int NMAX = 1e5 + 5;
constexpr LL CPF = 1e6;

int N, K;
int T[NMAX];

PLLI dp[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    for (int i = 1; i <= N; ++ i )
        cin >> T[i];
}

PLLI Check (LL costChange) {
    dp[1] = {CPF + costChange, 1};

    for (int i = 2; i <= N; ++ i ) {
        PLLI x, y;
        x = {dp[i-1].first + 1LL * ((T[i]+1) - (T[i-1]+1)) * CPF, dp[i-1].second};
        y = {dp[i-1].first + 1LL * costChange + 1LL * CPF, dp[i-1].second + 1};
        dp[i] = min(x, y);
    }

    return dp[N];
}

void Solve () {
    LL st = 0, dr = 1LL * 1e12;

    while (st <= dr) {
        LL mij = (st + dr) / 2;

        PLLI ans = Check(mij);

        if (ans.second == K) {
            cout << (ans.first - 1LL * ans.second * mij) / CPF << '\n';
            return;
        }

        if (ans.second > K) {
            st = mij + 1;
        }
        else dr = mij - 1;
    }

    PLLI ans = Check(st);

    cout << (ans.first - 1LL * K * st) / CPF << '\n';
}

void SolveNotAlien () {
    multiset <int> MS;
    for (int i = 2; i <= N; ++ i ) {
        MS.insert(T[i] - (T[i-1]+1));
    }

    int ans = N;
    for (int i = 1; i <= N-K; ++ i ) {
        int value = *(MS.begin());
        MS.erase(MS.begin());

        ans += value;
    }

    cout << ans << '\n';
}

int main () {
    Read();

    SolveNotAlien();
    //Solve();

    return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 472 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 472 KB Output is correct
16 Correct 44 ms 6260 KB Output is correct
17 Correct 34 ms 6360 KB Output is correct
18 Correct 33 ms 6348 KB Output is correct
19 Correct 33 ms 6240 KB Output is correct
20 Correct 36 ms 6388 KB Output is correct
21 Correct 42 ms 6304 KB Output is correct
22 Correct 40 ms 6332 KB Output is correct
23 Correct 38 ms 6372 KB Output is correct
24 Correct 34 ms 6284 KB Output is correct