oj.uz

Submission #930605

# Submission time Handle Problem Language Result Execution time Memory
930605 2024-02-20T07:48:15 Z ArgoCahaya Stove (JOI18_stove) C++14
20 / 100
 16 ms 29272 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3;
const int INF = 2e9;
int n, k;
int a[MAXN + 5];
int dp[MAXN + 100][MAXN + 100][3];

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 2 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14428 KB Output is correct
6 Correct 3 ms 14448 KB Output is correct
7 Correct 2 ms 14424 KB Output is correct
8 Correct 3 ms 14428 KB Output is correct
9 Correct 3 ms 14428 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 2 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14428 KB Output is correct
6 Correct 3 ms 14448 KB Output is correct
7 Correct 2 ms 14424 KB Output is correct
8 Correct 3 ms 14428 KB Output is correct
9 Correct 3 ms 14428 KB Output is correct
10 Runtime error 16 ms 29272 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14428 KB Output is correct
3 Correct 2 ms 14428 KB Output is correct
4 Correct 3 ms 14428 KB Output is correct
5 Correct 3 ms 14428 KB Output is correct
6 Correct 3 ms 14448 KB Output is correct
7 Correct 2 ms 14424 KB Output is correct
8 Correct 3 ms 14428 KB Output is correct
9 Correct 3 ms 14428 KB Output is correct
10 Runtime error 16 ms 29272 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -