oj.uz

답안 #1095189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1095189 2024-10-01T14:04:42 Z sunflower Stove (JOI18_stove) C++14
50 / 100
 104 ms 47676 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;
    subtask2 :: solve();

    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 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 468 KB Output is correct
5 Correct 0 ms 472 KB Output is correct
6 Correct 0 ms 344 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

# 결과 실행 시간 메모리 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 468 KB Output is correct
5 Correct 0 ms 472 KB Output is correct
6 Correct 0 ms 344 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 5 ms 12632 KB Output is correct
11 Correct 9 ms 13660 KB Output is correct
12 Correct 33 ms 24308 KB Output is correct
13 Correct 65 ms 35928 KB Output is correct
14 Correct 99 ms 46424 KB Output is correct
15 Correct 104 ms 47676 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 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 468 KB Output is correct
5 Correct 0 ms 472 KB Output is correct
6 Correct 0 ms 344 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 5 ms 12632 KB Output is correct
11 Correct 9 ms 13660 KB Output is correct
12 Correct 33 ms 24308 KB Output is correct
13 Correct 65 ms 35928 KB Output is correct
14 Correct 99 ms 46424 KB Output is correct
15 Correct 104 ms 47676 KB Output is correct
16 Runtime error 54 ms 43600 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -