Submission #1151731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151731		OI_Account	Split the sequence (APIO14_sequence)	C++20	71 / 100	2085 ms	83392 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100'000;
const int K = 200;
const ll INF = 1'000'000'000'000'000'000;
const int Q = 300'000;

int n, k, q;
ll a[N + 10], sum[N + 10];
ll dp[2][N + 10], val, valSum;
int res[K + 2][N + 10];
int l, r, t, row;

int pntL[Q + 10], pntR[Q + 10];
int minOpt[Q + 10], maxOpt[Q + 10];

void readInput() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    k++;   
}

ll getVal(int nl, int nr) {
    while (nl < l) {
        val += a[l - 1] * valSum;
        valSum += a[l - 1];
        l--;
    }
    while (r < nr) {
        val += a[r + 1] * valSum;
        valSum += a[r + 1];
        r++;
    }

    while (l < nl) {
        valSum -= a[l];
        val -= a[l] * valSum;
        l++;
    }
    while (nr < r) {
        valSum -= a[r];
        val -= a[r] * (valSum);
        r--;
    }

    return val;
}

inline void addQu(int l, int r, int x, int y) {
    q++;
    pntL[q] = l;
    pntR[q] = r;
    minOpt[q] = x;
    maxOpt[q] = y;
}

void solve(int l, int r, int optL, int optR) {
    int mid = (l + r) >> 1;
    dp[t][mid] = INF;
    int opt = optL;
    for (int i = optL; i <= optR && i < mid; i++) {
        ll tmp = dp[1 - t][i] + getVal(i + 1, mid);
        if (tmp <= dp[t][mid]) {
            dp[t][mid] = tmp;
            opt = i;
        }
    }
    res[row][mid] = opt;
    if (l < mid)
        addQu(l, mid - 1, optL, opt);
    if (mid < r)
        addQu(mid + 1, r, opt, optR);
}

void initVal() {
    l = r = 1;
    valSum = a[1];
    val = 0;
}

void calcDP() {
    initVal();
    for (int i = 1; i <= n; i++)
        dp[1][i] = getVal(1, i);
    for (int j = 2; j <= k; j++) {
        q = 1;
        pntL[1] = minOpt[1] = 1;
        pntR[1] = maxOpt[1] = n;
        t = j % 2;
        row = j;
        for (int i = 1; i <= q; i++)
            solve(pntL[i], pntR[i], minOpt[i], maxOpt[i]);
    }
}

void calcAns() {
    int pnt = n;
    vector<int> ans;
    for (int i = k; i >= 2; i--) {
        ans.push_back(res[i][pnt]);
        pnt = res[i][pnt];
    }
    sort(ans.begin(), ans.end());
    cout << getVal(1, n) - dp[k % 2][n] << '\n';
    for (auto x: ans)
        cout << x << ' ';
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcDP();
    calcAns();
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29