Submission #680972

#	Time	Username	Problem	Language	Result	Execution time	Memory
680972		Alexandruabcde	Stove (JOI18_stove)	C++14	20 / 100	1 ms	340 KiB

stove

#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 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50