Submission #1267602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267602		madamadam3	Stove (JOI18_stove)	C++20	50 / 100	150 ms	327680 KiB

stove

#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
int 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]--;
    }

    // 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]);
            // for (int j = 0; j < i; j++) {
            //     int cont = DP[s-1][j] + (times[i] - times[j+1] + 1);
            //     DP[s][i] = min(DP[s][i], cont);
            // }
            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