Submission #915854

#	Time	Username	Problem	Language	Result	Execution time	Memory
915854		Pekiban	Split the sequence (APIO14_sequence)	C++17	0 / 100	319 ms	82348 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int mxK = 202, mxN = 1e5+2;
int to[mxK][mxN], dq[mxN], l = 1, r = 1;
long long dpb[mxN], dp[mxN], pref[mxN];
inline 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 &&  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];
            while (r - l > 0 && 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) {
        cout << to[i][idx] << ' ';
        idx = to[i][idx];
    }
}

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