Submission #1099978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099978		vladilius	Split the sequence (APIO14_sequence)	C++17	50 / 100	2035 ms	24912 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
#define ld long double
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;
        }
    };
    deque<line> q;
    void add(int k, ll b, int i){
        q.pb({k, i, b});
    }
    pair<ll, int> get(int x){
        pair<ll, int> out = {inf, 0};
        for (line f: q){
            out = min(out, {f(x), f.i});
        }
        return out;
    }
    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;
    };
    
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1));
    vector<vector<int>> pr(n + 1, vector<int>(k + 1));
    for (int i = 1; i <= n; i++) dp[i][0] = 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], dp[i - 1][j - 1] + sq(p[i - 1]), i - 1);
            auto [x, ii] = T.get(p[i]);
            dp[i][j] = sq(p[i]) + x;
            pr[i][j] = ii;
        }
    }
    
    cout<<(1LL * p[n] * p[n] - dp[n][k]) / 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: 0 / 21
• Subtask 6: 0 / 29