Submission #916229

#	Time	Username	Problem	Language	Result	Execution time	Memory
916229		Alcabel	Split the sequence (APIO14_sequence)	C++17	0 / 100	27 ms	81944 KiB

sequence

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

struct Line {
    int a;
    long long b;
    int idx;
    Line() {}
    Line(int _a, long long _b, int _idx) {
        a = _a, b = _b, idx = _idx;
    }
    long long f(int x) {
        return a * 1ll * x + b;
    }
    ~Line() {}
};

int sign(long long x) {
    if (x > 0) { return 1; }
    if (x < 0) { return -1; }
    return 0;
}

long long intersect(const Line& A, const Line& B) {
    // A.a * x + A.b = B.a * x + B.b
    // x = (B.b - A.b) / (A.a - B.a)
    long long numer = B.b - A.b, denom = A.a - B.a;
    int sn = sign(numer), sd = sign(denom);
    numer *= sn, denom *= sd;
    if (sn * sd == -1) {
        return numer / denom * (-1);
    }
    return (numer + denom - 1) / denom;
}

struct CHT {
    vector<long long> optX;
    vector<Line> lines;
    int ptr;
    CHT() {
        ptr = 0;
    }
    void clear() {
        optX.clear();
        lines.clear();
        ptr = 0;
    }
    void insert(const Line& l) {
        if (!lines.empty() && lines.back().a == l.a) {
            if (l.b >= lines.back().b) {
                return;
            }
            lines.pop_back();
            optX.pop_back();
        }
        while (!lines.empty() && intersect(lines.back(), l) <= optX.back()) {
            lines.pop_back();
            optX.pop_back();
        }
        if (!lines.empty()) {
            optX.emplace_back(intersect(lines.back(), l));
            lines.emplace_back(l);
        } else {
            optX.emplace_back(-1);
            lines.emplace_back(l);
        }
    }
    pair<long long, int> getVal(int x) {
        ptr = min(ptr, (int)lines.size() - 1);
        while (ptr + 1 < (int)lines.size() && optX[ptr + 1] <= x) {
            ++ptr;
        }
        return {lines[ptr].f(x), lines[ptr].idx};
    }
    ~CHT() {}
};

const int maxn = 1e5, maxk = 201;
int par[maxn][maxk], dp[maxn][2];

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), pref(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        pref[i + 1] = pref[i] + a[i];
    }
    int layer = 0;
    for (int i = 0; i < n; ++i) {
        dp[i][0] = pref[i + 1] * 1ll * pref[i + 1];
        par[i][0] = -1;
    }
    CHT cht;
    for (int g = 1; g <= k; ++g) {
        // cerr << "g: " << g << '\n';
        layer ^= 1;
        cht.clear();
        pair<long long, int> res;
        for (int i = g; i < n; ++i) {
            // cerr << "i: " << i << '\n';
            cht.insert(Line(-2 * pref[i], dp[i - 1][layer ^ 1] + pref[i] * 1ll * pref[i], i - 1));
            // cerr << "inserted!\n";
            res = cht.getVal(pref[i + 1]);
            // cerr << "got!\n";
            // cerr << "res: " << res.first + pref[i + 1] * 1ll * pref[i + 1] << '\n';
            dp[i][layer] = res.first + pref[i + 1] * 1ll * pref[i + 1];
            par[i][g] = res.second;
        }
    }
    cout << (pref[n] * 1ll * pref[n] - dp[n - 1][layer]) / 2 << '\n';
    vector<int> ans;
    for (int i = n - 1, j = k; i >= 0 && j > 0; i = par[i][j], --j) {
        // cerr << "i: " << i << '\n';
        // cerr << "par: " << par[i][j] << '\n';
        ans.emplace_back(par[i][j] + 1);
    }
    reverse(ans.begin(), ans.end());
    for (const int& x : ans) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

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