Submission #868484

#	Time	Username	Problem	Language	Result	Execution time	Memory
868484		atom	Split the sequence (APIO14_sequence)	C++17	0 / 100	17 ms	80736 KiB

sequence

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, b) for(int i = 0; i < b; i++)
#define PER(i, b) for(int i = b - 1; i >= 0; i--)
#define fi first
#define se second
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
 
using pii = pair < int, int >;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int K = 205;
// Query for min;
struct ConvexHull {
    struct Line {
        ll a, b, id;
        Line (ll _a = 0, ll _b = 0, ll _id = -1) { a = _a; b = _b; id = _id; };
        ll cal(ll x) { return a * x + b; }
        long double cross(Line o) { return (long double) (b - o.b) / (long double) (o.a - a); }
    };
    deque <Line> q;
    void add(ll a, ll b, ll id) {
        Line nLine = Line(a, b, id);
        // need to change when a is increasing or decreasing
        while (q.size() >= 2 && q[q.size() - 1].cross(nLine) <= q[q.size() - 1].cross(q[q.size() - 2]))
            q.pop_back();
        q.push_back(nLine);
    }

    pair <ll, int> qry(ll x) {
        while (q.size() >= 2 && q[0].cal(x) <= q[1].cal(x))
            q.pop_front();
        return {q[0].cal(x), q[0].id};
    }
};
int n, k;
ll dp[2][N];
ll prf[N];
int opt[K][N];
// dp[i][k] = max j / (dp[j][k−1] + (pi − pj)⋅(pn − pi))
void run_case() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        prf[i] = prf[i - 1] + x;
    }
 
    // Base case, k = 0
    for (int step = 1; step <= k + 1; ++step) {
        ConvexHull hull;
        hull.add(0, 0, -1);

        for (int i = 1; i <= n; ++i) {
            ll x = prf[n] - prf[i];
            pair <ll, int> ret = hull.qry(x);
            dp[1][i] = ret.fi + prf[i] * x;
            opt[step][i] = ret.se;
            
            if (step != 1)
                hull.add(-prf[i], dp[0][i], i);
        }
        for (int i = 1; i <= n; ++i)
            dp[0][i] = dp[1][i];
    }
    cout << dp[0][n] << "\n";
    vector <int> ids;
    for (int i = k + 1, id = n; i > 0; --i) {
        if (id != n)
            ids.push_back(id);
        id = opt[i][id];
    }
    reverse(ids.begin(), ids.end());
    for (int x : ids) cout << x << " ";
    cout << "\n";
}
 
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif
 
    int Test = 1;
    //cin >> Test;
    for (int test = 1; test <= Test; test++){
 
        run_case();
    }
}

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