Submission #1127655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127655		thanhphu	K blocks (IZhO14_blocks)	C++20	0 / 100	0 ms	324 KiB

blocks

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

const long long inf = 1e18;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<vector<long long>> dp(k + 1, vector<long long>(n + 1, inf));
    dp[0][0] = 0;

    for (int x = 1; x <= k; ++x) {
        deque<int> dq;
        vector<long long> mx(n + 1, 0);

        for (int i = 1; i <= n; ++i) {
            while (!dq.empty() && dq.front() < i - 1) dq.pop_front();
            while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
            dq.push_back(i);
            mx[i] = a[dq.front()];
        }

        deque<int> q;
        q.push_back(0);

        for (int i = 1; i <= n; ++i) {
            while (!q.empty() && q.front() < i - 1) q.pop_front();
            dp[x][i] = dp[x - 1][q.front()] + mx[i];
            while (!q.empty() && dp[x - 1][q.back()] >= dp[x - 1][i]) q.pop_back();
            q.push_back(i);
        }
    }

    cout << dp[k][n] << endl;
    return 0;
}

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