Submission #1267601

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267601		madamadam3	Stove (JOI18_stove)	C++20	20 / 100	1097 ms	12104 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));
    for (int i = 0; i < n; i++) DP[1][i] = times[i] - times[0] + 1;

    for (int s = 2; s <= k; s++) {
        DP[s][0] = DP[1][0];

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

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