Submission #930607

#	Time	Username	Problem	Language	Result	Execution time	Memory
930607		ArgoCahaya	Stove (JOI18_stove)	C++14	50 / 100	1314 ms	262144 KiB

stove

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3;
const int INF = 2e9;
int n, k;
int a[MAXN + 5];
int dp[MAXN + 1][MAXN + 1][2];

int f(int idx, int cnt, int state)
{
    if (cnt > k)
        return INF;
    if (idx == n)
    {
        if (state == 1)
            return 0;
        else
        {
            if (cnt < k)
                return 1;
            return INF;
        }
    }

    int &ret = dp[idx][cnt][state];
    if (ret != -1)
        return ret;

    ret = INF;
    if (state)
    {
        ret = min(ret, f(idx + 1, cnt, 1) + (a[idx + 1] - a[idx]));
        ret = min(ret, f(idx + 1, cnt, 0) + (a[idx + 1] - a[idx]));
    }
    else
    {
        ret = min(ret, f(idx + 1, cnt + 1, 1) + 1);
        ret = min(ret, f(idx + 1, cnt + 1, 0) + 1);
    }
    return ret;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cout << f(0, 0, 0) << endl;
    return 0;
}

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