Submission #413814

#	Time	Username	Problem	Language	Result	Execution time	Memory
413814		illyakr	Stove (JOI18_stove)	C++14	50 / 100	136 ms	262148 KiB

stove

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<vector<int> > dp;
int pref = -1;
int main()
{
    cin >> n >> k;
    dp.resize(n + 2, vector<int>(k + 2, 1010101010));
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if (i == 1) {
            dp[i][1] = 1;
        } else {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j] + (a - pref);
                if (j > 1)dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
        pref = a;
    }
    int mn = 1010101010;
    for (int i = 1; i <= k; i++) {
        mn = min(mn, dp[n][i]);
//        cout << setw(2) << i << "  " << dp[n][i] << endl;
    }
    cout << mn;
}
/**
10 5
1
2
5
6
8
11
13
15
16
20

3 2
1 3 6
*/

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