Submission #1267077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267077		Art	Split the sequence (APIO14_sequence)	C++20	100 / 100	942 ms	82012 KiB

sequence

//      - Art -
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e5 + 7;
const int RANGE = 300;

template <class T1, class T2>
    bool maximize(T1 &a, T2 b) {
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b) {
        if (a > b) {a = b; return true;}
        return false;
    }

using namespace std;

int a[N], pre[N];
long long dp[N][2];
int where[N][202];

int sum(int l, int r) {
    return pre[r] - pre[l - 1];
}

namespace naive {
    long long dp[1002][202];

    void solve(int n, int k) {
        memset(dp, -0x3f, sizeof dp); // có thể có trường hợp sum(l,m)*sum(m+1,r)=0
        dp[0][0] = 0;
        FOR (x, 1, k + 1) FOR (i, 1, n) FOR (j, 1, i) {
            if (maximize(dp[i][x], dp[j - 1][x - 1] + 1ll * sum(j, i) * sum(i + 1, n))) {
                where[i][x] = j - 1;
            }
        }
        cout << dp[n][k + 1], el;

        int idx = n;
        REV (i, k + 1, 2) {
            cout << where[idx][i] << ' ';
            idx = where[idx][i];
        }
    }
}

namespace heuristic {

#define f(x)        (dp[(x) - 1][v] + 1ll * sum((x), i) * sum(i + 1, n))

    void solve(int n, int k) {
        bool u = 1, v = 0;
        FOR (x, 1, k + 1) {
            FOR (i, 1, n) {
                dp[i][u] = -1e18;
                int lo = 1, hi = i;
                while (lo <= hi) {
                    if (hi - lo <= RANGE) {
                        FOR (j, lo, hi) {
                            if (maximize(dp[i][u], f(j))) {
                                where[i][x] = j - 1;
                            }
                        }
                        break;
                    }
                    int m1 = lo + (hi - lo) / 3;
                    int m2 = hi - (hi - lo) / 3;
                    long long f1 = f(m1), f2 = f(m2);
                    if (maximize(dp[i][u], f1)) {
                        where[i][x] = m1 - 1;
                    }
                    if (maximize(dp[i][u], f2)) {
                        where[i][x] = m2 - 1;
                    }
                    if (f1 < f2) {
                        lo = m1 + 1;
                    }
                    else {
                        hi = m2 - 1;
                    }
                }
            }
            u ^= 1; v ^= 1;
        }
        cout << dp[n][v], el;

        int idx = n;
        REV (i, k + 1, 2) {
            cout << where[idx][i] << ' ';
            idx = where[idx][i];
        }
    }
}

namespace correct {
    void solve(int n, int k) {
        FOR (i, 1, n) {
            dp[i][1] = 1ll * pre[i] * (pre[n] - pre[i]);
        }
        FOR (c, 2, k) {
            auto calc = [&] (int j, long long x) {
                return pre[j] * x + -1ll * pre[j] * pre[n] + dp[j][!(c & 1)];
            };
            auto m = [&] (int x, int y) {
                return (double)(calc(x, 0) - calc(y, 0)) / (pre[y] - pre[x]);
            };
            deque<int> cht;
            int sz = 0;
            cht.emplace_back(c - 1); ++sz;
            FOR (i, c, n) {
                while (sz > 1 && calc(cht[0], pre[i]) <= calc(cht[1], pre[i])) {
                    cht.pop_front();
                    --sz;
                }
                dp[i][c & 1] = 1ll * pre[i] * (pre[n] - pre[i]) + calc(cht[0], pre[i]);
                where[i][c] = cht[0];
                while (sz > 0 && pre[cht[sz - 1]] == pre[i] && calc(cht[sz - 1], 0) <= calc(i, 0)) {
                    cht.pop_back(); --sz;
                }
                while (sz > 1 && m(cht[sz - 1], i) <= m(cht[sz - 1], cht[sz - 2])) {
                    cht.pop_back(); --sz;
                }
                cht.emplace_back(i); ++sz;
            }
        }
        long long mx = 0, idx = -1;
        FOR (i, k, n - 1) if (maximize(mx, dp[i][k & 1])) {
            idx = i;
        }
        cout << mx, el;
        REV (i, k, 1) {
            cout << idx << ' ';
            idx = where[idx][i];
        }
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;
    FOR (i, 1, n) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }

    if (n <= 1e3) {
        naive::solve(n, k);
        return 0;
    }

    if (n <= 1e4) {
        heuristic::solve(n, k);
        return 0;
    }

    correct::solve(n, k);

    return 0;
}

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