Submission #973134

#	Time	Username	Problem	Language	Result	Execution time	Memory
973134		oviyan_gandhi	Split the sequence (APIO14_sequence)	C++17	100 / 100	709 ms	82684 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], prv[N], curr[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.empty() && hull[0].m == l.m)
            hull.pop_front();
        while (hull.size() >= 2 && hull[1].isect(l) < hull[1].isect(hull[0]))
            hull.pop_front();
        hull.push_front(l);
    }

    pii query(int x){
        if (hull.empty()) return {0, 0};
        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];
    }
    int ans = 0;
    for (int l = 1; l <= k; l++){
        CHT hull;
        for (int i = 1; i <= n; i++){
            auto [v, j] = hull.query(ps[i]);
            dp[i][l] = j;
            ans = curr[i] = v;
            hull.add({ps[i], prv[i] - ps[i]*ps[i], i});
        }
        for (int i = 1; i <= n; i++) prv[i] = curr[i];
    }
    cout << ans << '\n';
    int curr = n;
    for (int i = k; i > 0; i--){
        cout << dp[curr][i] << ' ';
        curr = dp[curr][i];
    }
    cout << '\n';
    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