oj.uz

Submission #1095188

# Submission time Handle Problem Language Result Execution time Memory
1095188 2024-10-01T14:03:56 Z sunflower Stove (JOI18_stove) C++14
50 / 100
 96 ms 47452 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

int n, k;

const int maxn = (int) 1e5 + 7;

int a[maxn + 2];

namespace subtask1 {
    bool check() {
        return (n <= 20);
    }

    const int inf = (int) 1e9 + 7;
    const int N = (int) 20 + 7;

    int dp[N + 2][N + 2]; // dp[i][j]: tong time khi xet i nguoi dau tien va da bat k lan;

    void solve() {
        FOR(i, 0, n)
            FOR(j, 0, k) dp[i][j] = inf;

        dp[0][0] = 0;
        FOR(turn, 1, k) {
            FOR(i, 1, n) {
                FOR(j, 1, i) {
                    // use: i -> j;
                    minimize(dp[i][turn], dp[j - 1][turn - 1] + a[i] - a[j] + 1);
                }
            }
        }

        cout << dp[n][k];
    }
}

namespace subtask2 {
    bool check() {
        return (n <= 5000);
    }

    const int inf = (int) 1e9 + 7;
    const int N = (int) 5e3 + 7;

    int dp[N + 2][N + 2]; // dp[i][j]: tong time khi xet i nguoi dau tien va da bat k lan;
    int f[N + 2];

    void solve() {
        FOR(i, 0, n)
            FOR(j, 0, k) dp[i][j] = inf;

        dp[0][0] = 0;
        f[0] = 0;
        FOR(i, 1, n) f[i] = -a[1];

        FOR(turn, 1, k) {
            FOR(i, 1, n) {
                minimize(dp[i][turn], f[i] + a[i] + 1);
            }

            f[0] = inf;
            FOR(i, 1, n) f[i] = min(f[i - 1], dp[i - 1][turn] - a[i]);
        }

        cout << dp[n][k];
    }
}

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

    cin >> n >> k;
    FOR(i, 1, n) cin >> a[i];

    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    if (subtask2 :: check()) return subtask2 :: solve(), 0;

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6 ms 12636 KB Output is correct
11 Correct 7 ms 13660 KB Output is correct
12 Correct 34 ms 24156 KB Output is correct
13 Correct 71 ms 35932 KB Output is correct
14 Correct 96 ms 46424 KB Output is correct
15 Correct 96 ms 47452 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 6 ms 12636 KB Output is correct
11 Correct 7 ms 13660 KB Output is correct
12 Correct 34 ms 24156 KB Output is correct
13 Correct 71 ms 35932 KB Output is correct
14 Correct 96 ms 46424 KB Output is correct
15 Correct 96 ms 47452 KB Output is correct
16 Incorrect 8 ms 1624 KB Output isn't correct
17 Halted 0 ms 0 KB -