Submission #383525

#	Time	Username	Problem	Language	Result	Execution time	Memory
383525		danielcm585	Split the sequence (APIO14_sequence)	C++14	0 / 100	88 ms	131072 KiB

sequence

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

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;

const int N = 1e5;
const int K = 2e2;
const ll INF = 1e18;
int n, k;
ll a[N+2], sum[N+2];
ll dp[N+5][K+5], bt[N+5][K+5];

struct line {
    ll m, c, id;

    ll operator ()(ll x) {
        return m*x+c;
    }
};

struct convexHull {
    int sz;
    vector<line> v;

    void reset() {
        v.clear();
        sz = 0;
    }

    bool greaterFrac(ld a, ld b, ld c, ld d) {
        return a/b >= c/d;
    }

    bool isBad(line a, line b, line c) {
        // (c1-c2)/(m2-m1) >= (c2-c3)/(m3-m2)
        return greaterFrac(a.c-b.c,b.m-a.m,b.c-c.c,c.m-b.m);
    }

    void insert(ll m, ll c, int id) {
        line x = {m,c,id};
        while (sz >= 2 && isBad(v[sz-2],v[sz-1],x)) {
            v.pop_back(); sz--;
        }
        v.push_back(x); sz++;
    }

    ii query(ll x) {
        ll ret = -INF, id = -1;
        for (int l = 0, r = sz-1; l <= r; ) {
            int mid = (l+r)/2;
            if (ret < v[mid](x)) {
                ret = v[mid](x);
                id = v[mid].id;
            }
            if (mid+1 < sz && v[mid+1](x) > v[mid](x)) l = mid+1;
            else r = mid-1;
        }
        return {ret,id};
    }

} ch;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k; k++;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1]+a[i];
    }
    for (int i = 2; i <= k; i++) {
        ch.reset();
        for (int j = 1; j <= i-1; j++) dp[j][i] = -INF;
        for (int j = i; j <= n; j++) {
            ch.insert(sum[j-1],dp[j-1][i-1]-sum[j-1]*sum[j-1],j-1);
            ii x = ch.query(sum[j]);
            dp[j][i] = x.fi;
            bt[j][i] = x.se;
        }
    }
    vector<int> res;
    for (int i = n, j = k; i >= 1; i = bt[i][j], j--) {
        res.push_back(bt[i][j]);
    }
    reverse(res.begin(),res.end());
    cout << dp[n][k] << '\n';
    for (int i = 1; i < res.size(); i++) {
        if (i != 1) cout << ' ';
        cout << res[i];
    }
    cout << '\n';
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int i = 1; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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