Submission #915870

#	Time	Username	Problem	Language	Result	Execution time	Memory
915870		Pekiban	Split the sequence (APIO14_sequence)	C++17	100 / 100	455 ms	82028 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int mxK = 202, mxN = 1e5+2;
bool vis[mxN];
int to[mxK][mxN], dq[mxN], l = 0, r = 0;
long long dpb[mxN], dp[mxN], pref[mxN];
long long sq(long long a) {
    return a*a;
}
double cord(int x, int y) {
    return (double)(dpb[x] - sq(pref[x]) - dpb[y] + sq(pref[y]))/(pref[y] - pref[x]);// (d-b)/(a-c)
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        pref[i] = pref[i-1] + x;
    }
    for (int i = 1; i <= k; ++i) {
        dq[0] = r = l = 0;
        for (int j = 1; j <= n; ++j) {
            while (r - l > 0 && pref[j] != pref[j-1] && cord(dq[l], dq[l+1]) <= pref[j])   l++;
            dp[j] = dpb[dq[l]] - sq(pref[dq[l]]) + pref[dq[l]] * pref[j];
            to[i][j] = dq[l];
            if (pref[j] != pref[dq[r-1]]) {
                while (r - l > 0 && pref[j] != pref[dq[r-1]] && cord(dq[r-1], j) <= cord(dq[r], dq[r-1]))  r--;
                dq[++r] = j;
            } 
        }
        for (int j = 1; j <= n; ++j) {
            dpb[j] = dp[j];
        }
    }
    cout << dp[n] << '\n';
    int idx = n;
    for (int i = k; i >= 1; --i) {
        if (!to[i][idx]) {
            for (int j = n-1; j >= 1 && i >= 1; --j){
                if (!vis[j]) {
                    --i;
                    cout << j << ' ';
                }
            }
            break;
        }
        cout << to[i][idx] << ' ';
        idx = to[i][idx];
        vis[idx] = 1;
    }
}

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