oj.uz

Submission #680972

# Submission time Handle Problem Language Result Execution time Memory
680972 2023-01-12T07:17:57 Z Alexandruabcde Stove (JOI18_stove) C++14
20 / 100
 1 ms 340 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';
}

int main () {
    Read();

    Solve();

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -