Submission #677792

#	Time	Username	Problem	Language	Result	Execution time	Memory
677792		vicious	Split the sequence (APIO14_sequence)	C++17	71 / 100	564 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll,ll> pi;
typedef tuple<int,int,int> ti;  
template<typename T> bool chmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int N = 100010;
int n,k;
ll a[N],s[N],dp[N],par[210][N];

struct CHT {
    deque<pi> dq;
    deque<int> idx;
    ll f(pi line, ll x) {
        return line.first*x + line.second;
    }
    pi query(ll x) {
        while(dq.size()>1) {
            if(f(dq[0],x)<f(dq[1],x)) {
                dq.pop_front();
                idx.pop_front();
            } else {
                break;
            }
        }
        return {f(dq[0],x), idx[0]};
    }
    double intersect(ll m1, ll c1, ll m2, ll c2) {
        return (double) (c2-c1)/(m1-m2);
    }
    double intersect(pi a, pi b) {
        return intersect(a.first,a.second,b.first,b.second);
    }
    void insert(ll m, ll c, int id) {
        pi line = {m,c};
        while(dq.size() > 1) {
            int s = dq.size();
            if(intersect(dq[s-1],line) <= intersect(dq[s-2],line)) {
                dq.pop_back();
                idx.pop_back();
            } else {
                break;
            }
        }
        dq.push_back(line);
        idx.push_back(id);
    }
    void clear() {
        while (dq.size()) dq.pop_front();
        while (idx.size()) idx.pop_front();
    }
} ch;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin.exceptions(ios::badbit|ios::failbit);
    cin >> n >> k;   
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = n; i >= 1; --i) s[i]=s[i+1]+a[i];
    for (int j = 1; j <= k; ++j) {
        vector<ll> new_dp(n+1);
        vector<int> new_par(n+1);
        for (int i = n; i > 1; --i) {
            if (j>n-i+1) continue;
            ch.insert(s[i],(ll)dp[i]-(ll)s[i]*(ll)s[i],i);
            new_dp[i-1] = ch.query(s[i-1]).first;
            new_par[i-1] = ch.query(s[i-1]).second;
        }
        for (int i = n; i >= 1; --i) {
            dp[i]=new_dp[i];
            par[j][i]=new_par[i];
        }
        ch.clear();
    }
    int ptr = 1;
    vector<int> seq;
    while (ptr) {
        ptr = par[k--][ptr];
        if (ptr) seq.push_back(ptr-1);
    }
    cout << dp[1] << '\n';
    for (auto i: seq) cout << i << ' ';
    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