oj.uz

Submission #917026

# Submission time Handle Problem Language Result Execution time Memory
917026 2024-01-27T02:33:26 Z atom K blocks (IZhO14_blocks) C++17
0 / 100
 16 ms 86872 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 1e5 + 5;
const int K = 17;
const int M = 105;

int rmq[K][N];
int lg[N];
int get(int l, int r) {
    int k = lg[r - l + 1];
    return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
int n, m;
int a[N];
ll dp[M][N];

void solve(int x, int l, int r, int opt_l, int opt_r) {
    if (l > r) return;
    int mi = (l + r) >> 1;
    ll ans = 1e18;
    int split = -1;
    for (int i = opt_l; i <= min(mi, opt_r); ++i) {
        ll curAns = dp[x - 1][i] + get(i + 1, mi);
        if (curAns < ans) {
            ans = curAns;
            split = i;
        }
    }
    dp[x][mi] = ans;
    solve(x, l, mi - 1, opt_l, split);
    solve(x, mi + 1, r, split, opt_r);
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) rmq[0][i] = a[i];
    for (int k = 1; k < K; ++k) {
        int step = 1 << (k - 1);
        for (int i = 1; i + step <= n; ++i)
            rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + step]);
    }

    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; ++i) {
        dp[1][i] = get(1, i);
        // debug(dp[1][i]);
    }
    for (int i = 2; i <= m; ++i) {  
        solve(i, 1, n, 1, n);
        // for (int j = 1; j <= n; ++j) {
        //     debug(dp[i][j]);
        // }
    }
    cout << dp[m][n] << "\n";
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 84568 KB Output is correct
2 Correct 14 ms 84572 KB Output is correct
3 Correct 13 ms 84776 KB Output is correct
4 Correct 14 ms 84572 KB Output is correct
5 Correct 14 ms 84648 KB Output is correct
6 Correct 14 ms 84572 KB Output is correct
7 Correct 13 ms 84572 KB Output is correct
8 Correct 15 ms 86620 KB Output is correct
9 Correct 14 ms 86684 KB Output is correct
10 Incorrect 14 ms 86872 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 84716 KB Output is correct
2 Correct 13 ms 84572 KB Output is correct
3 Correct 15 ms 84576 KB Output is correct
4 Correct 14 ms 84572 KB Output is correct
5 Correct 14 ms 84732 KB Output is correct
6 Correct 14 ms 84760 KB Output is correct
7 Correct 14 ms 84732 KB Output is correct
8 Correct 15 ms 86620 KB Output is correct
9 Correct 13 ms 86724 KB Output is correct
10 Incorrect 14 ms 86616 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 84568 KB Output is correct
2 Correct 14 ms 84572 KB Output is correct
3 Correct 13 ms 84776 KB Output is correct
4 Correct 14 ms 84572 KB Output is correct
5 Correct 14 ms 84648 KB Output is correct
6 Correct 14 ms 84572 KB Output is correct
7 Correct 13 ms 84572 KB Output is correct
8 Correct 15 ms 86620 KB Output is correct
9 Correct 14 ms 86684 KB Output is correct
10 Incorrect 14 ms 86872 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 84568 KB Output is correct
2 Correct 14 ms 84572 KB Output is correct
3 Correct 13 ms 84776 KB Output is correct
4 Correct 14 ms 84572 KB Output is correct
5 Correct 14 ms 84648 KB Output is correct
6 Correct 14 ms 84572 KB Output is correct
7 Correct 13 ms 84572 KB Output is correct
8 Correct 15 ms 86620 KB Output is correct
9 Correct 14 ms 86684 KB Output is correct
10 Incorrect 14 ms 86872 KB Output isn't correct
11 Halted 0 ms 0 KB -