Submission #638054

#	Time	Username	Problem	Language	Result	Execution time	Memory
638054		tvladm2009	K blocks (IZhO14_blocks)	C++14	100 / 100	475 ms	48416 KiB

blocks

#include <iostream>
#include <stack>
 
using namespace std;
 
const int MAX_N = 1e5;
const int MAX_K = 1e2;
const int MAX_L = 17;
const int INF = (1 << 30);
int a[MAX_N + 1], l[MAX_N + 1];
int dp[MAX_N + 1][MAX_K + 1], rmq[MAX_L + 1][MAX_N + 1], log[MAX_N + 1];
int n, k;
 
void precalc() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[i] >= a[st.top()]) {
            st.pop();
        }
        if (st.empty()) {
            l[i] = 0;
        } else {
            l[i] = st.top();
        }
        st.push(i);
    }
}
 
void build()  {
    for (int i = 1; i <= MAX_L; i++) {
        for (int j = 1; j <= n; j++) {
            if (j + (1 << (i - 1)) <= n) {
                rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
}
 
int query(int l, int r) {
    int p = log[r - l + 1];
    return min(rmq[p][l], rmq[p][r - (1 << p) + 1]);
}
 
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = INF;
        }
    }
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        mx = max(mx, a[i]);
        dp[i][1] = mx;
    }
    precalc();
    for (int i = 2; i <= MAX_N; i++) {
        log[i] = log[i >> 1] + 1;
    }
    for (int blocks = 2; blocks <= k; blocks++) {
        for (int i = 1; i <= n; i++) {
            rmq[0][i] = dp[i][blocks - 1];
        }
        build();
        for (int i = blocks; i <= n; i++) {
            if (l[i] == 0) {
                dp[i][blocks] = a[i] + query(1, i - 1);
            } else {
                dp[i][blocks] = min(dp[l[i]][blocks], a[i] + query(l[i], i - 1));
            }
        }
    }
    cout << dp[n][k];
    return 0;
}

Compilation message (stderr)

blocks.cpp:11:58: warning: built-in function 'log' declared as non-function [-Wbuiltin-declaration-mismatch]
   11 | int dp[MAX_N + 1][MAX_K + 1], rmq[MAX_L + 1][MAX_N + 1], log[MAX_N + 1];
      |                                                          ^~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47