Submission #868457

#	Time	Username	Problem	Language	Result	Execution time	Memory
868457		atom	Split the sequence (APIO14_sequence)	C++17	0 / 100	71 ms	7348 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 int INF = 1e9;
    const int MOD = 1e9 + 7;
    const int N = 1e5 + 5;
    const int K = 205;
     
    struct CHT {
        // Querying for max
        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;
        /*
            Decreasing slope;
            add: >= 
            Increasing slope;
            add: <=
        */
        void add(ll a, ll b, ll id) {
            Line nLine = Line(a, b, id);
            while (q.size() >= 2 && q[0].cross(nLine) >= q[0].cross(q[1]))
                q.pop_front();
            q.push_front(nLine);
        }
        pair <ll, int> qry(ll x) {
            int l = 0, r = (int) q.size() - 1;
            while (l < r) {
                int m = (l + r) / 2;
                if (q[m].cal(x) < q[m + 1].cal(x))
                    l = m + 1;
                else
                    r = m;
            }
            return {q[l].cal(x), q[l].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 i = 1; i <= n; ++i) {
            dp[0][i] = (prf[i] - prf[0]) * (prf[n] - prf[i]);
            opt[1][i] = i;
        }
        
        for (int step = 1; step <= k; ++step) {
            CHT hull;
            hull.add(0, 0, 0);
            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;
     
                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";
     

    }
     
    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