oj.uz

답안 #652674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
652674 2022-10-23T17:20:40 Z Neos K개의 묶음 (IZhO14_blocks) C++14
0 / 100
 43 ms 84076 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> ii;

const int N = 1e5 + 7, M = 107;

int n, k, a[N], L[N], dp[N][M];
stack<int> st;

int T[N][M];
void upd(int i, int j, int v) {
    for (; i <= n; i += i & -i)
        T[i][j] = min(T[i][j], v);
}

int get(int i, int l, int r) {
    int res = 2e9;
    while (l <= r) {
        if (r - (r & -r) >= l) {
            res = min(res, T[r][i]);
            r -= r & -r;
        }
        else {
            res = min(res, dp[r][i]);
            --r;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(dp, 0x3f, sizeof dp);
    memset(T, 0x3f, sizeof T);
    dp[0][1] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][1] = max(dp[i - 1][1], a[i]);
        upd(i, 1, dp[i][1]);
    }
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] <= a[i]) st.pop();
        if (st.empty()) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = get(j - 1, 1, i) + a[i];
                upd(i, j, dp[i][j]);
            }
        }
        else {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = min(get(j - 1, st.top() + 1, i) + a[i], dp[L[i] - 1][j - 1] + a[L[i]]);
                upd(i, j, dp[i][j]);
            }
        }
        st.push(i);

        // f(i, j) = min(f(k - 1, j - 1) + max(a[k]..a[i]))
    }
    cout << dp[n][k];
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 84044 KB Output is correct
2 Correct 38 ms 83960 KB Output is correct
3 Correct 41 ms 84016 KB Output is correct
4 Correct 38 ms 84072 KB Output is correct
5 Correct 38 ms 84044 KB Output is correct
6 Correct 37 ms 83992 KB Output is correct
7 Correct 42 ms 84036 KB Output is correct
8 Correct 38 ms 84020 KB Output is correct
9 Correct 37 ms 84040 KB Output is correct
10 Incorrect 38 ms 84044 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 83992 KB Output is correct
2 Correct 35 ms 84064 KB Output is correct
3 Correct 42 ms 84044 KB Output is correct
4 Correct 38 ms 84064 KB Output is correct
5 Correct 42 ms 84076 KB Output is correct
6 Correct 39 ms 83984 KB Output is correct
7 Correct 36 ms 84000 KB Output is correct
8 Correct 36 ms 84064 KB Output is correct
9 Correct 40 ms 83964 KB Output is correct
10 Incorrect 43 ms 83972 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 84044 KB Output is correct
2 Correct 38 ms 83960 KB Output is correct
3 Correct 41 ms 84016 KB Output is correct
4 Correct 38 ms 84072 KB Output is correct
5 Correct 38 ms 84044 KB Output is correct
6 Correct 37 ms 83992 KB Output is correct
7 Correct 42 ms 84036 KB Output is correct
8 Correct 38 ms 84020 KB Output is correct
9 Correct 37 ms 84040 KB Output is correct
10 Incorrect 38 ms 84044 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 84044 KB Output is correct
2 Correct 38 ms 83960 KB Output is correct
3 Correct 41 ms 84016 KB Output is correct
4 Correct 38 ms 84072 KB Output is correct
5 Correct 38 ms 84044 KB Output is correct
6 Correct 37 ms 83992 KB Output is correct
7 Correct 42 ms 84036 KB Output is correct
8 Correct 38 ms 84020 KB Output is correct
9 Correct 37 ms 84040 KB Output is correct
10 Incorrect 38 ms 84044 KB Output isn't correct
11 Halted 0 ms 0 KB -