oj.uz

Submission #930604

# Submission time Handle Problem Language Result Execution time Memory
930604 2024-02-20T07:46:50 Z ArgoCahaya Stove (JOI18_stove) C++14
0 / 100
 2 ms 9820 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3;
const int INF = INT_MAX;
int n, k;
int a[MAXN + 5];
int dp[MAXN + 100][MAXN + 100][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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -