Submission #973088

#	Time	Username	Problem	Language	Result	Execution time	Memory
973088		oviyan_gandhi	Split the sequence (APIO14_sequence)	C++17	89 / 100	749 ms	84784 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int32_t> pii;

#define N 100001
#define K 201
int ps[N];
int32_t dp[N][K];

struct Frac {
    int n, d;
    Frac(int num, int den) : n{num}, d{den} { if (d < 0) n = -n, d = -d; }
    bool operator < (const Frac &o) const { return __int128_t(n)*__int128_t(o.d) < __int128_t(o.n)*__int128_t(d); }
};

struct Line {
    int m, c, i;
    Frac isect(const Line &o) const { return {c - o.c, o.m - m}; }
    int operator () (const int x) const { return m*x + c; }
};

struct CHT {
    deque<Line> hull;

    void add(Line l){
        while (hull.size() >= 2 && hull[1].isect(l) < hull[1].isect(hull[0]))
            hull.pop_front();
        hull.push_front(l);
    }

    pii query(int x){
        while (hull.size() >= 2 && hull.back()(x) <= hull[hull.size()-2](x))
            hull.pop_back();
        return {hull.back()(x), hull.back().i};
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> ps[i];
        ps[i] += ps[i-1];
    }
    ps[0] = -1;
    CHT prv;
    for (int i = 1; i < n; i++)
        if (ps[i] != ps[i-1])
            prv.add({ps[i], -ps[i]*ps[i], i});
    int ans = 0;
    for (int l = 1; l <= k; l++){
        CHT curr;
        for (int i = 1; i <= n; i++){
            if (ps[i] == ps[i-1]) continue;
            auto [v, j] = prv.query(ps[i]);
            dp[i][l] = j;
            ans = v;
            if (i < n)
                curr.add({ps[i], v - ps[i]*ps[i], i});
        }
        prv = curr;
    }
    cout << ans << '\n';
    int curr = n;
    for (int i = k; i > 0; i--){
        while (ps[curr] == ps[curr-1]) curr--;
        cout << dp[curr][i] << ' ';
        curr = dp[curr][i];
    }
    cout << '\n';
    return 0;
}

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