Submission #735490

#	Time	Username	Problem	Language	Result	Execution time	Memory
735490		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	45 ms	16696 KiB

sequence

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

class cht_t {
       public:
        class line_t {
               public:
                int64_t a, b;
                line_t(int64_t a, int64_t b) : a(a), b(b) {}
                int64_t operator()(const int& x) const { return a * x + b; }
                friend bool check(const line_t& origin, const line_t& lhs, const line_t& rhs) {
                        return 1.0 * (rhs.a - origin.a) / (origin.b - rhs.b) < 1.0 * (lhs.a - origin.a) / (origin.b - lhs.b);
                }
        };
        deque<pair<line_t, int>> dq;

        void insert(int64_t a, int64_t b, int id) {
                line_t newline(a, b);
                while (dq.size() > 1 && check(dq[dq.size() - 2].first, dq.back().first, newline)) dq.pop_back();
                dq.emplace_back(newline, id);
        }

        pair<int64_t, int> getmin(const int64_t& x) {
                while (dq.size() > 1 && dq[0].first(x) > dq[1].first(x)) dq.pop_front();
                return {dq[0].first(x), dq[0].second};
        }
};

int main() {
        int n, k;
        cin >> n >> k;
        k++;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int64_t res = 1ll * accumulate(a.begin(), a.end(), 0ll) * accumulate(a.begin(), a.end(), 0ll);
        for (int i = 0; i < n; i++) res -= 1ll * a[i] * a[i];
        // f[i][j] = min(f[k][j - 1] + (ps[i] - ps[k]) * (ps[i] - ps[k]))
        // f[i][j] = min(f[k][j - 1] + ps[k] * ps[k] + pss[k] - 2 * ps[k] * ps[i]) + ps[i] * ps[i] - pss[i];
        //                -----------------v-----------------   ----v----  ---v---
        //                                 b                        a         x
        vector<vector<int64_t>> f(n, vector<int64_t>(k));
        vector<vector<int>> trace(n, vector<int>(k));
        vector<cht_t> cht(k);
        int64_t ps = 0, pss = 0;
        for (int i = 0; i < n; i++) {
                ps += a[i], pss += 1ll * a[i] * a[i];
                for (int j = k - 1; j >= 0; j--) {
                        if (j > i) continue;
                        if (j) {
                                auto p = cht[j - 1].getmin(ps);
                                f[i][j] = p.first + ps * ps - pss;
                                trace[i][j] = p.second;
                        } else {
                                f[i][j] = ps * ps - pss;
                                trace[i][j] = -1;
                        }
                        cht[j].insert(-2 * ps, f[i][j] + ps * ps + pss, i);
                }
        }
        vector<int> ans;
        int ii = n - 1, jj = k - 1;
        while (ii != -1) ans.emplace_back(trace[ii][jj] + 1), ii = trace[ii][jj], jj--;
        ans.pop_back();
        reverse(ans.begin(), ans.end());
        cout << (res - f[n - 1][k - 1]) / 2 << '\n';
        for (int x : ans) cout << x << ' ';
}

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