Thử nghiệm Robot THT Bảng B 2021

#include <iostream>
#include <algorithm>
#include <functional>
#include <queue>

using namespace std;
using ll = long long;

constexpr int N = 1e3 + 5;
constexpr ll Inf = 1e17 + 7;
int n, m, a[N];
ll dp[N][N], c[N][N];

void Read()
{
    cin >> n >> m;

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

}

void DAC(int l, int r, int optl, int optr, int j) {
    if(l > r) return;
    if(optl == optr) {
        for(; l <= r; ++l)
            if(optl <= l)
                dp[l][j] = max(dp[optl - 1][j - 1], c[optl][l]);
        return;
    }

    int mid = (l + r) / 2, optmid = 1;

    for(int i = optl; i <= optr && i <= mid; ++i)
        if(dp[mid][j] > max(dp[i - 1][j - 1], c[i][mid])) {
            dp[mid][j] = max(dp[i - 1][j - 1], c[i][mid]);
            optmid = i;
        }

    //cout << mid << " " << optmid << "\n";

    DAC(l, mid - 1, optl, optmid, j);
    DAC(mid + 1, r, optmid, optr, j);
}

void Solve() {
    /// Calculate c()
    for(int i = 1; i <= n; ++i) {
        // Hang doi uu tien
        priority_queue<int> prefix;
        priority_queue<int, vector<int>, greater<int>> suffix;
        // Tong cac phan tu trong hai hang doi uu tien
        ll s = 0, p = 0;

        for(int j = i; j; --j) {
            if(prefix.empty() || a[j] <= prefix.top()) {
                prefix.emplace(a[j]);
                p += a[j];
            }
            else {
                suffix.emplace(a[j]);
                s += a[j];
            }
            // |prefix| == |suffix| + 2
            if((int)prefix.size() == (int)suffix.size() + 2) {
                p -= prefix.top();
                s += prefix.top();
                suffix.emplace(prefix.top());
                prefix.pop();
            }
            // |prefix| == |suffix| - 1
            else if((int)prefix.size() == (int)suffix.size() - 1) {
                s -= suffix.top();
                p += suffix.top();
                prefix.emplace(suffix.top());
                suffix.pop();
            }

            int x = prefix.top();
            c[j][i] = (1ll * x * prefix.size() - p) + (s - 1ll * suffix.size() * x);
        }
    }

    ///Calculate dp
    fill_n(&dp[0][0], N * N, Inf);
    dp[0][0] = 0;

    for(int j = 1; j <= m; ++j)
        DAC(1, n, 1, n, j);

    cout << dp[n][m];
}

int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Read();
    Solve();
}