Submission #973674

#	Time	Username	Problem	Language	Result	Execution time	Memory
973674		avighna	Split the sequence (APIO14_sequence)	C++17	100 / 100	649 ms	82648 KiB

sequence

#include <bits/stdc++.h>

typedef long long ll;

const ll N = 1e5 + 1, K = 201;
const ll inf = 1e15;

ll dp[2][N];
int back[K][N];
ll a[N], psum[N];

 
ll sum(ll a, ll b) {
    if (a > b) {
        return 0;
    }
    ll ans = psum[b];
    if (a - 1 >= 0) {
        ans -= psum[a - 1];
    }
    return ans;
}

struct Line {
    ll m, b;
    ll idx;

    ll eval(ll x) {
        return m * x + b;
    }
};

class CHT {
private:
    bool parallel(const Line &a, const Line &b) {
        return a.m == b.m;
    }
    long double x_intersection(const Line &a, const Line &b) {
        return (a.b - b.b) / ((long double) (b.m - a.m));
    }

public:
    std::deque<Line> dq;

    void insert(Line l) {
        if (dq.size() >= 1 && parallel(l, dq.back()) && l.b <= dq.back().b) {
            return;
        }
        while (dq.size() >= 2) {
            if (parallel(l, dq.back())) {
                if (l.b > dq.front().b) {
                    dq.pop_front();
                    continue;
                } else {
                    return;
                }
            }
            if (x_intersection(l, dq.back()) <= x_intersection(dq.back(), dq[dq.size() - 2])) {
                dq.pop_back();
            } else {
                break;
            }
        }
        if (dq.size() == 1 && parallel(l, dq.back()) && l.b > dq.back().b) {
            dq.pop_back();
        }
        dq.push_back(l);
    }

    std::pair<ll, int> query(ll x) {
        while (dq.size() >= 2 && dq[0].eval(x) <= dq[1].eval(x)) {
            dq.pop_front();
        }
        return {dq[0].eval(x), dq[0].idx};
    }
};

int main() {
    ll n, k;
    std::cin >> n >> k;
    for (ll i = 0; i < n; ++ i) {
        std::cin >> a[i];
    }
    std::partial_sum(a, a + n, psum);

    if (n == 2) {
        std::cout << a[0] * a[1] << "\n1\n";
        return 0;
    }

    for (ll i = 0; i <= k; ++ i) {
        CHT hull;
        for (ll j = n - 1; j >= 0; -- j) {
            if (j == n - 1) {
                dp[i % 2][j] = -inf * (i != 0);
                continue;
            }
            if (i == 0) {
                dp[i % 2][j] = 0;
                continue;
            }

            hull.insert({sum(j + 1, n - 1), dp[(i + 1) % 2][j + 1] + sum(0, j) * sum(j + 1, n - 1), j + 1});
            std::pair<ll, int> q = hull.query(-sum(0, j - 1));
            dp[i % 2][j] = std::max(0LL, q.first);
            back[i][j] = q.second;
        }
    }

    std::cout << dp[k % 2][0] << "\n";
    ll ops = k;
    ll cur = 0;
    while (ops > 0) {
        std::cout << back[ops][cur] << " ";
        cur = back[ops][cur];
        ops--;
    }
    std::cout << "\n";
}

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