Submission #1099983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099983		vladilius	Split the sequence (APIO14_sequence)	C++17	100 / 100	820 ms	83028 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();
 
struct CHT{
    struct line{
        int k, i; ll b;
        ll operator () (int x){
            return 1LL * k * x + b;
        }
    };
    double inter(line x, line y){
        return (double) (x.b - y.b) / (y.k - x.k);
    }
    deque<line> q;
    void add(int k, ll b, int i){
        line f = {k, i, b};
        while (q.size() > 1 && inter(q.back(), q[q.size() - 2]) >= inter(q[q.size() - 2], f)){
            q.pop_back();
        }
        if (!q.empty() && q.back().k == f.k){
            if (q.back().b > f.b){
                q.pop_back();
            }
            else {
                return;
            }
        }
        q.pb(f);
    }
    pair<ll, int> get(int x){
        while (q.size() > 1 && inter(q[0], q[1]) < x) q.pop_front();
        return {q[0](x), q[0].i};
    }
    void clear(){
        q.clear();
    }
};
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k; cin>>n>>k;
    vector<int> a(n + 1), p(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        p[i] = p[i - 1] + a[i];
    }
    
    auto sq = [&](int x){
        return 1LL * x * x;
    };
    
    ll dp1[n + 1], dp2[n + 1];
    int pr[n + 1][k + 1];
    for (int i = 1; i <= n; i++) dp1[i] = sq(p[i]);
    CHT T;
    for (int j = 1; j <= k; j++){
        T.clear();
        for (int i = j + 1; i <= n; i++){
            T.add(-2 * p[i - 1], dp1[i - 1] + sq(p[i - 1]), i - 1);
            auto [x, ii] = T.get(p[i]);
            dp2[i] = sq(p[i]) + x;
            pr[i][j] = ii;
        }
        for (int i = 1; i <= n; i++) dp1[i] = dp2[i];
    }
    
    cout<<(1LL * p[n] * p[n] - dp1[n]) / 2<<"\n";
    vector<int> all;
    while (k > 0){
        all.pb(pr[n][k]);
        n = all.back(); k--;
    }
    reverse(all.begin(), all.end());
    for (int i: all) cout<<i<<" ";
}

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