제출 #1267753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267753		madamadam3	Stove (JOI18_stove)	C++20	100 / 100	31 ms	3572 KiB

stove

#include <bits/stdc++.h>

using namespace std;

#define int long long int
using pi = pair<int, int>;
const int INF = 4e18;

signed main() { // is this alien trick ??
    cin.tie(0)->sync_with_stdio(0);

    int n, k; cin >> n >> k;
    vector<int> times(n); 

    for (int i = 0; i < n; i++) {
        cin >> times[i]; 
        times[i]--;
    }

    auto g = [&](int la) {
        vector<int> DP(n, INF), cnt(n, -INF), prefix_min(n+1, INF);
        DP[0] = 1+la; cnt[0] = 1;

        int pb = 0, pc = 0, pv = -times[0] + 1 + la;

        for (int i = 1; i < n; i++) {
            int cand = DP[i-1] - times[i] + 1 + la;
            if (cand < pv || cand == pv && cnt[i-1] < pc) {
                pc = cnt[i-1];
                pv = cand;
                pb = i;
            }

            DP[i] = times[i] + pv;
            cnt[i] = pc+1;
        }

        return make_pair(DP[n-1], cnt[n-1]);
    };

    int lo = 0, hi = 1e9;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        
        pi fx = g(mid);
        if (fx.second > k) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }

    pi r1 = g(lo), r2 = g(lo-1);
    cout << max(r1.first - k * lo, r2.first - k * (lo-1)) << "\n";

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50