Submission #1267619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267619		madamadam3	Stove (JOI18_stove)	C++20	50 / 100	1095 ms	2628 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);
        DP[0] = 1+la; cnt[0] = 1;

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

        // cout << "λ = " << la << " DP = " ; for (auto &el : DP) cout << el << " "; cout << "\n";
        // cout << "DP[n-1] = " << DP[n-1] << " cnt[n-1] = " << cnt[n-1] << "\n";
        return make_pair(DP[n-1], cnt[n-1]);
    };

    int lo = 0, hi = 1e18;
    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";

    // DP[k][i] = minimum cost to cover everything up to person i, using exactly k segments
    // DP[1][i] = times[i] - times[0] + 1
    // DP[k>1][i] = min(DP[k-1][i], DP[k-1][j] + times[i] - times[j+1] + 1) for j < i

    // vector<vector<int>> DP(k+1, vector<int>(n, INF));
    // vector<vector<int>> prefix_min(k+1, vector<int>(n+1, INF));
    // for (int i = 0; i < n; i++) {
    //     DP[1][i] = times[i] - times[0] + 1;
    //     if (i < n - 1) prefix_min[1][i+1] = min(prefix_min[1][i], DP[1][i] - times[i+1] + 1);
    // }

    // for (int s = 2; s <= k; s++) {
    //     DP[s][0] = DP[1][0];
    //     prefix_min[s][1] = min(prefix_min[s][0], DP[s][0] - times[1] + 1);

    //     for (int i = 1; i < n; i++) {
    //         DP[s][i] = min(DP[s-1][i], prefix_min[s-1][i] + times[i]);
    //         if (i < n - 1) prefix_min[s][i+1] = min(prefix_min[s][i], DP[s][i] - times[i+1] + 1);
    //     }
    // }
    
    // cout << DP[k][n-1] << "\n";
    return 0;
}

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