Submission #973013

#	Time	Username	Problem	Language	Result	Execution time	Memory
973013		oviyan_gandhi	Split the sequence (APIO14_sequence)	C++17	0 / 100	1 ms	348 KiB

sequence

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

#define N 100001
#define K 201
int ps[N];
pii 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;
    return n == 1;
    for (int i = 1; i <= n; i++){
        cin >> ps[i];
        ps[i] += ps[i-1];
    }
    CHT prv;
    for (int i = 1; i <= n; i++){
        if (ps[i] == ps[i-1]) continue;
        prv.add({ps[i], -ps[i]*ps[i], i});
    }
    for (int l = 1; l <= k; l++){
        CHT curr;
        for (int i = 1; i <= n; i++){
            if (ps[i] == ps[i-1]) continue;
            dp[i][l] = prv.query(ps[i]);
            curr.add({ps[i], dp[i][l].first - ps[i]*ps[i], i});
        }
        prv = curr;
    }
    cout << dp[n][k].first << '\n';
    int curr = n;
    for (int i = k; i > 0; i--){
        cout << dp[curr][i].second << ' ';
        curr = dp[curr][i].second;
    }
    cout << '\n';
    return 0;
}

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