제출 #680974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
680974		Alexandruabcde	Stove (JOI18_stove)	C++14	100 / 100	44 ms	6388 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';
}

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