Submission #779090

#	Time	Username	Problem	Language	Result	Execution time	Memory
779090		vjudge1	Stove (JOI18_stove)	C++17	50 / 100	1012 ms	1452 KiB

stove

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector <int> dp, v;

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

//    freopen("stove.in", "r", stdin);
//    freopen("stove.out", "w", stdout);

    cin >> n >> k;
    dp.resize(n + 1, INT_MAX);
    v.resize(n + 1);

    dp[1] = 1;

    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    for(int i = 2; i <= n; i ++)
    {
        int last = min(k, i);
        for(int j = last; j >= 2; j --)
        {
            if(dp[j] != INT_MAX)
                dp[j] = min(dp[j] + v[i] - v[i - 1], dp[j - 1] + 1);
            else
                dp[j] = dp[j - 1] + 1;
        }
        dp[1] = dp[1] + v[i] - v[i - 1];

    }

    cout << dp[k];
    return 0;
}

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