Submission #1288579

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

sequence

#include<bits/stdc++.h>
using namespace std;

const long long NEG = LLONG_MIN/4;

struct Line {
    long long m, b;
    int id;
    Line(long long _m=0, long long _b=0, int _id=0): m(_m), b(_b), id(_id) {}
};

inline bool bad(const Line &l1, const Line &l2, const Line &l3){
    return (l3.b - l1.b) * (l1.m - l2.m) <= (l2.b - l1.b) * (l1.m - l3.m);
}

struct CHT {
    vector<Line> hull;
    int ptr = 0;

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

    void add(Line L){
        while(!hull.empty() && hull.back().m == L.m){
            if (hull.back().b >= L.b) return;
            hull.pop_back();
        }
        while(hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), L))
            hull.pop_back();
        hull.push_back(L);
        ptr = min(ptr, (int)hull.size()-1);
    }

    Line query(long long x){
        while(ptr + 1 < (int)hull.size() && 
              hull[ptr].m * x + hull[ptr].b <= hull[ptr+1].m * x + hull[ptr+1].b)
            ptr++;
        return hull[ptr];
    }
};

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

    CHT current, next;
    vector<vector<int>> trace(k + 1, vector<int>(n + 1, 0));
    
    current.add(Line(0, 0, 0));
    
    long long res = LLONG_MIN;
    int bestEnd = -1;

    for (int j = 1; j <= k; ++j){
        next.clear();
        for (int i = j; i <= n; ++i){
            Line best = current.query(pre[i] - pre[n]);
            if (best.b == NEG) continue;
            
            long long dp = best.b + pre[i] * (pre[n] - pre[i]);
            trace[j][i] = best.id;
            
            if (j < k) {
                next.add(Line(pre[i], dp, i));
            }
            if (j == k && i < n && dp > res){
                res = dp;
                bestEnd = i;
            }
        }
        swap(current, next);
    }

    cout << res << '\n';
    
    vector<int> cuts;
    int cur = bestEnd;
    for (int j = k; j >= 1 && cur > 0; --j){
        cuts.push_back(cur);
        cur = trace[j][cur];
    }
    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