Submission #503714

#	Time	Username	Problem	Language	Result	Execution time	Memory
503714		fvogel499	Split the sequence (APIO14_sequence)	C++14	100 / 100	897 ms	83700 KiB

sequence

/*
 * File created on 01/08/2022 at 17:20:18.
 * Link to problem: 
 * Description: 
 * Time complexity: O()
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2022 Francois Vogel
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

#define mp pair<pii, int>
#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define int ll
#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int inf = 1e18;

ld xIntersection(int a1, int b1, int a2, int b2) {
    return (ld)(b1-b2)/(ld)(a2-a1);
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    int n, kConst;
    cin >> n >> kConst;
    int b [n];
    for (int i = 0; i < n; i++) cin >> b[i];
    int p [n];
    p[0] = b[0];
    for (int i = 1; i < n; i++) p[i] = p[i-1]+b[i];
    int sum = p[n-1];
    int pdp [n+1];
    int ndp [n+1];
    for (int i = 0; i < n; i++) pdp[i] = -inf;
    pdp[n] = 0;
    signed to [kConst+1][n];
    for (int i = 0; i <= kConst; i++) {
        deque<mp> q;
        for (int j = n-1; j >= 0; j--) {
            int slope = 2*p[j];
            int xint = p[j]*sum-p[j]*p[j]+pdp[j+1];
            while (size(q) >= 2 && xIntersection(q[0].f.f, q[0].f.s, q[1].f.f, q[1].f.s) <= xIntersection(q[1].f.f, q[1].f.s, slope, xint)) {
                q.pop_front();
            }
            q.push_front(mp(pii(slope, xint), j+1));
            int query = 0;
            if (j) query = p[j-1];
            while (size(q) >= 2 && q[size(q)-2].f.f*query+q[size(q)-2].f.s >= q.back().f.f*query+q.back().f.s) {
                q.pop_back();
            }
            to[i][j] = q.back().s;
            ndp[j] = q.back().f.f*query+q.back().f.s;
            if (j) ndp[j] -= p[j-1]*sum+p[j-1]*p[j-1];
        }
        for (int j = 0; j < n; j++) pdp[j] = ndp[j];
        pdp[n] = -inf;
    }
    cout << pdp[0]/2 << '\n';
    vi res;
    int x = 0;
    for (int i = kConst; i > 0; i--) {
        x = to[i][x];
        res.pb(x);
    }
    for (int i : res) cout << i << ' ';

    cout.flush();
    int d = 0;
    d++;
}

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