Submission #1190723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190723		g4yuhg	Split the sequence (APIO14_sequence)	C++20	22 / 100	1 ms	584 KiB

sequence

#include<bits/stdc++.h>
typedef long long ll;
#define fi first
#define se second
#define pii pair<ll,ll>
#define endl '\n'
#define N 100005
#define inf 1e18
using namespace std;
int n, k, a[N], where[N][202];
ll f[N][2], pf[N];
vector<ll> A, B, C;
bool bad(ll l1, ll l2, ll l3) {
    return (B[l1] - B[l2]) * (A[l3] - A[l1]) <= (B[l3] - B[l1]) * (A[l1] - A[l2]);
}

void add(ll u, ll v, ll id) {
    A.push_back(u);
    B.push_back(v);
    C.push_back(id);
    while (A.size() >= 3 && bad(A.size() - 3, A.size() - 2, A.size() - 1)) {
        A.erase(A.end() - 2);
        B.erase(B.end() - 2);
        C.erase(C.end() - 2);
    }
}

ll cal(pii u, ll x) {
    return u.fi * x + u.se;
}
ll ptr = 0;
pii get(ll x) {
    if (ptr >= A.size()) {
        ptr = A.size() - 1;
        return {cal({A[ptr], B[ptr]}, x), C[ptr]};
    }
    while (ptr < A.size() - 1 && cal({A[ptr], B[ptr]}, x) < cal({A[ptr + 1], B[ptr + 1]}, x)) {
        //cout << cal({A[ptr], B[ptr]}, x) << " " << cal({A[ptr + 1], B[ptr + 1]}, x) << endl;
        ptr ++ ;
    }
    //cout << endl;
    return {cal({A[ptr], B[ptr]}, x), C[ptr]};
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pf[i] = pf[i - 1] + a[i];
    }

    for (int z = 0; z <= k; z++) {
        A.clear();
        B.clear();
        C.clear();
        ptr = 0;
        for (int i = n; i >= 1; i--) {
            if (i > n) {
                f[i][z % 2] = -inf;
                continue;
            }
            if (z == 0) {
                f[i][z % 2] = 0;
                continue;
            }
            if (z > 0 && i < n) {
                add(pf[i], -(pf[i] * pf[i]) + pf[n] * pf[i] + f[i + 1][1 - (z % 2)], i);
            }
            if (i < n) {
            	pii xet = get(pf[i - 1]);
                f[i][z % 2] = xet.fi - pf[n] * pf[i - 1];
                where[i][z] = xet.se;
            }
        }
    }
    cout << f[1][k % 2] << endl;
    ll cur = 1, curk = k;
    while (true) {
    	cur = where[cur][curk] + 1;
    	cout << cur - 1 << " ";
    	curk -- ;
    	if (curk <= 0) break;
    }
    return 0;
}

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