Submission #1288575

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

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN / 4;

struct Line {
    ll m; // slope
    ll b; // intercept
    int id; // index that produced this line
    Line(ll _m=0, ll _b=0, int _id=0): m(_m), b(_b), id(_id) {}
};

bool bad(const Line &l1, const Line &l2, const Line &l3){
    // check if l2 is unnecessary between l1 and l3
    // (b3 - b1) / (m1 - m3) <= (b2 - b1) / (m1 - m2)
    // cross multiply, use __int128 to avoid overflow
    __int128 left  = (__int128)(l3.b - l1.b) * (__int128)(l1.m - l2.m);
    __int128 right = (__int128)(l2.b - l1.b) * (__int128)(l1.m - l3.m);
    return left <= right;
}

struct CHT {
    vector<Line> hull;
    int ptr = 0; // pointer for queries with increasing x

    void clear(){ hull.clear(); ptr = 0; }

    void add(Line L){ // slopes must be non-decreasing
        while(hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), L))
            hull.pop_back();
        hull.push_back(L);
        if (ptr >= (int)hull.size()) ptr = hull.size() - 1;
    }

    // query for maximum at x; x queries must be non-decreasing across calls
    pair<ll,int> query(ll x){
        if (hull.empty()) return {NEG, 0};
        while(ptr + 1 < (int)hull.size()){
            __int128 v1 = (__int128)hull[ptr].m * x + (__int128)hull[ptr].b;
            __int128 v2 = (__int128)hull[ptr+1].m * x + (__int128)hull[ptr+1].b;
            if (v2 >= v1) ++ptr;
            else break;
        }
        ll val = (ll)((__int128)hull[ptr].m * x + (__int128)hull[ptr].b);
        return {val, hull[ptr].id};
    }
};

// build and return CHT hull for level (K-1) using items i = 1..upto
// (we follow the same insertion rule as original: when computing dp_j at layer j, we insert into lc[j] only if j < K)
CHT build_lc_last(const vector<ll> &pre, int n, int K, int upto){
    // K is the current k we want to query for (so we want lc[K-1] with lines from dp_{K-1})
    vector<CHT> lc(K+1); // indices 0..K
    lc[0].add(Line(0, 0, 0)); // base
    for (int i = 1; i <= upto; ++i){
        int mxj = min(i, K);
        // iterate j desc to avoid using newly inserted lines in same i
        for (int j = mxj; j >= 1; --j){
            auto g = lc[j-1].query(pre[i] - pre[n]);
            if (g.first == NEG) continue;
            ll dp = g.first + pre[i] * (pre[n] - pre[i]);
            if (j < K) lc[j].add(Line(pre[i], dp, i));
        }
    }
    // return copy of lc[K-1]
    return lc[K-1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<ll> a(n+1);
    vector<ll> pre(n+1, 0);
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }

    ll res = NEG;
    int bestPos = 0;

    // initial full run to find best result and bestPos
    vector<CHT> lc(k+1);
    lc[0].add(Line(0, 0, 0));
    for (int i = 1; i <= n; ++i){
        int mxj = min(i, k);
        for (int j = mxj; j >= 1; --j){
            auto g = lc[j-1].query(pre[i] - pre[n]);
            if (g.first == NEG) continue;
            ll dp = g.first + pre[i] * (pre[n] - pre[i]);
            if (j < k) lc[j].add(Line(pre[i], dp, i));
            if (j == k && i < n && dp > res){
                res = dp;
                bestPos = i;
            }
        }
    }

    if (res == NEG) {
        // If there's no valid splitting (edge cases), print something reasonable:
        // Depending on problem, could be 0 and no cuts; here print 0 and nothing.
        cout << 0 << "\n";
        return 0;
    }

    cout << res << "\n";

    // reconstruct cuts by recomputing hulls up to bestPos-1 for each step
    vector<int> cuts;
    int rem = k;
    int curPos = bestPos;
    while (rem > 0 && curPos > 0){
        cuts.push_back(curPos);
        // build hulls up to level rem-1 using items up to curPos-1
        if (rem == 0) break;
        CHT ch = build_lc_last(pre, n, rem, curPos - 1);
        // query ch at x = pre[curPos] - pre[n] to get predecessor id
        auto g = ch.query(pre[curPos] - pre[n]);
        int prev = g.second; // might be 0 (base)
        curPos = prev;
        --rem;
    }

    reverse(cuts.begin(), cuts.end());
    for (int i = 0; i < (int)cuts.size(); ++i){
        if (i) cout << ' ';
        cout << cuts[i];
    }
    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