Submission #1226610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226610		395333em	Split the sequence (APIO14_sequence)	C++20	22 / 100	13 ms	4932 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>

using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int LR = 1e12 + 5;
const int N = 1e5 + 5;
const int K = 2e2 + 5;

int n, k, a[N], pref[N], dp[K][N], pos[K][N];

struct line {
    int m, c;
    line(int m, int c) : m(m), c(c) {}
    int cal(int x){
        return m * x + c;
    }
};

struct lichaotree {
    struct node {
        line val;
        int idx;
        node *l, *r;
        node(line val, int idx) : val(val), idx(idx), l(0), r(0) {}
    };
    typedef node* pnode;
    pnode root;
    void update(int l, int r, pnode &i, line cur, int idx){
        if (!i) return i = new node(cur, idx), void();
        int mid = (l + r) / 2;
        if (cur.cal(mid) > i->val.cal(mid)) swap(cur, i->val), swap(i->idx, idx);
        if (cur.cal(l) > i->val.cal(l)) update(l, mid, i->l, cur, idx);
        if (cur.cal(r) > i->val.cal(r)) update(mid + 1, r, i->r, cur, idx);
    }
    pii query(int l, int r, pnode &i, int x){
        if (!i) return {0, 0};
        int mid = (l + r) / 2;
        if (x <= mid) return max(make_pair(i->val.cal(x), i->idx), query(l, mid, i->l, x));
        else return max(make_pair(i->val.cal(x), i->idx), query(mid + 1, r, i->r, x));
    }
} lct;

signed main(){
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], pref[i] = pref[i - 1] + a[i];
    for (int i = 1; i <= n; i++) dp[0][i] = -inf;
    for (int i = 1; i <= k; i++) {
        lct.root = 0;
        lct.update(-LR, LR, lct.root, line(0, 0), 0);
        for (int j = 1; j <= n; j++) {
            pii curr = lct.query(-LR, LR, lct.root, pref[n] - pref[j]);
            curr.first += pref[j] * pref[n] - pref[j] * pref[j];
            dp[i][j] = curr.first;
            pos[i][j] = curr.second;
            lct.update(-LR, LR, lct.root, line(-pref[j], dp[i - 1][j]), j);
            // cout << i << ", " << j << " : " << dp[i][j] << ", " << pos[i][j] << "\n";
        }
    }
    int ans = -inf, idx = 0, curk = k;
    for (int i = 1; i < n; i++) {
        if (dp[k][i] >= ans) ans = dp[k][i], idx = i;
    }
    cout << ans << "\n";
    while (curk > 0) {
        cout << idx << " ";
        idx = pos[curk--][idx];
    }
}

/*

*ORDER OF SPLIT DOESN'T MATTER*

dp[i][j] = max score after splitting i'th round at after position j
dp[i][j] = max(dp[i - 1][k] + (pref[j] - pref[k]) * (pref[n] - pref[j]))
dp[i][j] = max(dp[i - 1][k] + pref[j] * pref[n] - pref[j]^2 - pref[k] * pref[n] + pref[k] * pref[j])
dp[i][j] = pref[j] * pref[n] - pref[j]^2 + max(dp[i - 1][k] - pref[k] * (pref[n] - pref[j]))

const = pref[j] * pref[n] - pref[j]^2
m = -pref[k]
x = pref[n] - pref[j]
c = dp[i - 1][k]

*/

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