Submission #1190831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190831		g4yuhg	Split the sequence (APIO14_sequence)	C++20	100 / 100	1257 ms	84712 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(int l1, int l2, int l3) {
    return (B[l1] - B[l2]) * (A[l3] - A[l1]) <= (B[l3] - B[l1]) * (A[l1] - A[l2]);
}

deque<int> dq;

ll cal(int id, ll x) {
    return A[id] * x + B[id];
}
// pf[i]
// -pf[i] * pf[i] + pf[n] * pf[i] + f[i + 1][1 - (z % 2)]
void add(ll u, ll v, ll idx) {
	A.push_back(u);
	B.push_back(v);
	C.push_back(idx);
	ll id = A.size() - 1;
	while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq[dq.size() - 1], id)) {
		dq.pop_back();
	}
	dq.push_back(id); // ta khong can pop tai A, B, C, vi dq luu chi so, va gio chi can luu nhu vay
}
pii get(ll x) {
	while (dq.size() >= 2 && cal(dq[0], x) < cal(dq[1], x)) {
		dq.pop_front();
	}
	return {cal(dq[0], x), C[dq[0]]};
}
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();
        dq.clear();
        for (int i = n; i >= 1; i--) {
            if (z == 0) {
                f[i][z % 2] = 0;
                continue;
            }
            if (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;
            }
            else {
            	f[i][z % 2] = -inf;
            }
        }
    }
    cout << f[1][k % 2] << endl;
    ll cur = 1, curk = k;
    while (curk > 0) {
        cur = where[cur][curk] + 1;
        cout << cur - 1 << " ";
        curk--;
    }
    return 0;
}

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