Submission #1288545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288545		harryleee	Split the sequence (APIO14_sequence)	C++20	71 / 100	2097 ms	72152 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = (ll)-9e18;
const ll INF = (ll)9e18;

int n, k;
vector<ll> a, pre;

// parentPacked: lưu (k+2) x (n+1) entries, mỗi entry 3 bytes (little-endian)
vector<unsigned char> parentPacked;

inline void set_parent(int layer, int idx, int val){
    size_t pos = ((size_t)layer * (n + 1) + idx) * 3;
    parentPacked[pos]     = (unsigned char)(val & 0xFF);
    parentPacked[pos + 1] = (unsigned char)((val >> 8) & 0xFF);
    parentPacked[pos + 2] = (unsigned char)((val >> 16) & 0xFF);
}
inline int get_parent(int layer, int idx){
    size_t pos = ((size_t)layer * (n + 1) + idx) * 3;
    int v = parentPacked[pos] | (parentPacked[pos + 1] << 8) | (parentPacked[pos + 2] << 16);
    return v;
}

struct line{
    long long a, b;
    mutable long double p;
    int id;
    bool operator < (const line& other) const {
        if (other.a == (long long)1e18 && other.b == (long long)1e18)
            return p < other.p;
        return a < other.a || (a == other.a && b < other.b);
    }
};

struct LINE_CONTAINER {
    multiset<line> ms;
    inline bool del(multiset<line>::iterator x, multiset<line>::iterator y){
        if (y == ms.end()){
            x->p = 1e18;
            return false;
        }
        if (x->a == y->a){
            x->p = (x->b >= y->b) ? 1e18 : -1e18;
        } else {
            x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
        }
        return x->p >= y->p;
    }
    inline void update(long long a, long long b, int i){
        auto x = ms.insert({a,b,0.0L,i});
        auto y = next(x);
        while (del(x,y)) y = ms.erase(y);
        if (x != ms.begin()){
            y = prev(x);
            if (del(y,x)) ms.erase(x);
        } else y = x;
        while (y != ms.begin()){
            x = prev(y);
            if (del(x,y)){
                del(x, ms.erase(y));
                y = x;
            } else break;
        }
    }
    inline pair<long long,int> get(long long x){
        auto it = ms.lower_bound({(long long)1e18, (long long)1e18, (long double)x, 0});
        if (it == ms.end()) return {NEG_INF, 0};
        return { it->a * x + it->b, it->id };
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> k)) return 0;
    a.assign(n+1,0);
    pre.assign(n+1,0);
    for (int i = 1; i <= n; ++i){ cin >> a[i]; pre[i] = pre[i-1] + a[i]; }

    // allocate packed parents: (k+2) layers * (n+1) entries * 3 bytes
    parentPacked.assign((size_t)(k + 2) * (n + 1) * 3, 0);

    // dp only 2 layers
    vector<ll> dp_prev(n+1, INF), dp_cur(n+1, INF);
    dp_prev[0] = 0;

    for (int c = 1; c <= k + 1; ++c){
        LINE_CONTAINER lc;
        // insert t=0 if valid
        if (dp_prev[0] < INF/4) lc.update(2LL * pre[0], -(dp_prev[0] + pre[0]*pre[0]), 0);

        // reset dp_cur
        fill(dp_cur.begin(), dp_cur.end(), INF);

        for (int i = 1; i <= n; ++i){
            auto g = lc.get(pre[i]);
            if (g.first != NEG_INF){
                ll val = pre[i]*pre[i] - g.first;
                if (val < dp_cur[i]){
                    dp_cur[i] = val;
                    // store parent t = g.second into packed array
                    set_parent(c, i, g.second);
                }
            }
            // add line for t = i to be used later
            if (dp_prev[i] < INF/4){
                ll slope = 2LL * pre[i];
                ll intercept = -(dp_prev[i] + pre[i]*pre[i]);
                lc.update(slope, intercept, i);
            }
        }
        dp_prev.swap(dp_cur);
    }

    ll total = pre[n] * pre[n];
    ll min_sumsq = dp_prev[n]; // dp[n][k+1]
    ll best_points = (total - min_sumsq) / 2;
    cout << best_points << '\n';

    // backtrack using packed parents
    vector<int> cuts;
    int cur = n;
    int layer = k + 1;
    while (layer > 0 && cur > 0){
        int prev = get_parent(layer, cur);
        if (prev == 0) break;
        cuts.push_back(prev);
        cur = prev;
        --layer;
    }
    reverse(cuts.begin(), cuts.end());
    // print first k cuts (between 1..n-1). (cuts size should be k)
    for (size_t i = 0; i < cuts.size() && (int)i < k; ++i){
        if (i) cout << ' ';
        cout << cuts[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: 0 / 29