Submission #1288539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288539		harryleee	Split the sequence (APIO14_sequence)	C++20	11 / 100	1 ms	584 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5;
int n, k;
ll a[MAXN + 1], pre[MAXN + 1];
int trace[MAXN + 1][201];
ll dp[MAXN + 1][201];
int bestPos = 0;

struct Line {
    ll a, b;
    mutable long double p;
    int id;
    bool operator<(const Line& other) const { return a < other.a || (a == other.a && b < other.b); }
    bool operator<(long double x) const { return p < x; } // heterogeneous lookup
};

struct LINE_CONTAINER {
    multiset<Line, less<>> ms;
    static constexpr long double INF = 1e30L;

    bool isect(multiset<Line, less<>>::iterator x, multiset<Line, less<>>::iterator y) {
        if (y == ms.end()) {
            x->p = INF;
            return false;
        }
        if (x->a == y->a) {
            x->p = (x->b >= y->b ? INF : -INF);
        } else {
            x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
        }
        return x->p >= y->p;
    }

    void add(ll slope, ll intercept, int id) {
        auto it = ms.insert({slope, intercept, 0.0L, id});
        auto z = next(it);
        while (isect(it, z)) z = ms.erase(z);
        if (it != ms.begin()) {
            auto y = prev(it);
            if (isect(y, it)) { ms.erase(it); return; }
        }
        auto y = it;
        while (y != ms.begin()) {
            auto x = prev(y);
            if (isect(x, y)) {
                isect(x, ms.erase(y));
                y = x;
            } else break;
        }
    }

    // trả về {value, id} hoặc {NEG,0} nếu rỗng
    pair<ll,int> query(ll X) {
        if (ms.empty()) return {LLONG_MIN/4, 0};
        auto it = ms.lower_bound((long double)X); // dùng operator<(long double)
        if (it == ms.end()) --it;
        // tính bằng __int128 để tránh overflow
        __int128 val = (__int128)it->a * (__int128)X + (__int128)it->b;
        ll out;
        if (val > ( (__int128)LLONG_MAX )) out = LLONG_MAX;
        else if (val < ( (__int128)LLONG_MIN )) out = LLONG_MIN;
        else out = (ll)val;
        return {out, it->id};
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> k)) return 0;
    for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i-1] + a[i]; }

    const ll NEG = LLONG_MIN / 4;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j) {
            dp[i][j] = NEG;
            trace[i][j] = 0;
        }
    dp[0][0] = 0;

    vector<LINE_CONTAINER> lc(max(1, k)); // containers for j = 0..k-1
    lc[0].add(0LL, 0LL, 0);

    for (int i = 1; i <= n; ++i) {
        // duyệt j giảm để tránh dùng chính dòng vừa thêm trong cùng i
        for (int j = min(i, k); j >= 1; --j) {
            auto g = lc[j-1].query(pre[n] - pre[i]);
            if (g.first > NEG/2) {
                // tính an toàn với __int128
                __int128 tmp = (__int128)g.first + (__int128)pre[i] * (__int128)(pre[n] - pre[i]);
                ll val;
                if (tmp > (__int128)LLONG_MAX) val = LLONG_MAX;
                else if (tmp < (__int128)LLONG_MIN) val = LLONG_MIN;
                else val = (ll)tmp;
                dp[i][j] = val;
                trace[i][j] = g.second; // lưu id chỉ khi dp hợp lệ
                if (j < k && dp[i][j] > NEG/2) lc[j].add(-pre[i], dp[i][j], i);
                if (j == k && i < n && dp[i][k] > dp[bestPos][k]) bestPos = i;
            }         }
    }

    cout << dp[bestPos][k] << '\n';
    int curPos = bestPos, curK = k;
    vector<int> cuts;
    while (curPos != 0 && curK > 0) {
        cuts.push_back(curPos);
        int prev = trace[curPos][curK];
        curPos = prev;
        --curK;
    }
    reverse(cuts.begin(), cuts.end());
    for (int x : cuts) cout << x << ' ';
    cout << '\n';
    return 0;
}

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