oj.uz

Submission #1095206

# Submission time Handle Problem Language Result Execution time Memory
1095206 2024-10-01T14:56:03 Z sunflower Stove (JOI18_stove) C++14
100 / 100
 73 ms 51548 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];
    }
}

namespace subtask3 {
    void solve() {
        vector <int> v;
        FOR(i, 1, n - 1) v.push_back(a[i + 1] - 1 - a[i]);

        sort(v.begin(), v.end(), greater <int> ());
        int ans = a[n] - a[1] + 1;
        FOR(i, 1, k - 1) ans -= v[i - 1];

        cout << ans;
    }
}

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;
    subtask3 :: solve();

    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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 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 600 KB Output is correct
9 Correct 1 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 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 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 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 28764 KB Output is correct
11 Correct 7 ms 29532 KB Output is correct
12 Correct 27 ms 36444 KB Output is correct
13 Correct 47 ms 44892 KB Output is correct
14 Correct 70 ms 51036 KB Output is correct
15 Correct 73 ms 51548 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 468 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 600 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 7 ms 28764 KB Output is correct
11 Correct 7 ms 29532 KB Output is correct
12 Correct 27 ms 36444 KB Output is correct
13 Correct 47 ms 44892 KB Output is correct
14 Correct 70 ms 51036 KB Output is correct
15 Correct 73 ms 51548 KB Output is correct
16 Correct 13 ms 2272 KB Output is correct
17 Correct 13 ms 2308 KB Output is correct
18 Correct 14 ms 2268 KB Output is correct
19 Correct 13 ms 2272 KB Output is correct
20 Correct 13 ms 2268 KB Output is correct
21 Correct 13 ms 2268 KB Output is correct
22 Correct 13 ms 2272 KB Output is correct
23 Correct 13 ms 2272 KB Output is correct
24 Correct 14 ms 2460 KB Output is correct