Submission #1133500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133500		totoro	Split the sequence (APIO14_sequence)	C++20	71 / 100	106 ms	196608 KiB

sequence

#include <iostream>
#include <vector>
#include <utility>

const long long INF = 1000000000000000ll;

struct ConvexHull {
    std::vector<std::pair<long long, long long>> lines;
    std::vector<std::pair<long long, long long>> intervals; // inclusive, line[l] is the GOAT for intervals[l].first..intervals[l].second
    std::vector<int> index;
    int total = 0;
    int ptr = 0;
    void push(std::pair<long long, long long> line);
    void emplace(long long m, long long c) {push(std::make_pair(m, c));}
    long long querymax(long long u, int* sz);
};

std::pair<long long, long long> intersect(std::pair<long long, long long> l1, std::pair<long long, long long> l2) {
    if (l1.first == l2.first) return {INF, INF};
    long long left = (l2.second - l1.second) / (l1.first - l2.first);
    long long right = (l2.second - l1.second - 1) / (l1.first - l2.first) + 1;
    return {left, right};
}

long long apply(std::pair<long long, long long> l, long long u) {
    return l.first * u + l.second;
}

void ConvexHull::push(std::pair<long long, long long> line) {
    if (lines.empty()) {
        lines.push_back(line);
        intervals.emplace_back(-INF, INF);
        index.push_back(total++);
        return;
    }
    while (lines.size() - ptr >= 2) {
        auto isct = intersect(line, lines[lines.size()-2]);
        long long startrange = isct.second;
        if (startrange < intervals.back().first) {
            lines.pop_back();
            intervals.pop_back();
            intervals.back().second = isct.first;
            index.pop_back();
        } else {
            break;
        }
    }
    auto isct = intersect(line, lines.back());
    lines.push_back(line);
    intervals.emplace_back(isct.second, INF);
    index.push_back(total++);
}

long long ConvexHull::querymax(long long u, int* sz) {
    while (lines.size() - ptr >= 2) {
        long long now = apply(lines[ptr], u);
        long long next = apply(lines[ptr+1], u);
        if (next > now) ++ptr;
        else break;
    }
    *sz = index[ptr];
    return (apply(lines[ptr], u));
}

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<long long> v(n);
    for (int i = 0; i < n; ++i) std::cin >> v[i];
    std::vector<long long> p(n + 1);
    for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + v[i - 1];
    /*
        dp[kk][i] is the best value using kk splits with last one 'at' i
        so if we know dp[kk-1] for all i, then we can calculate dp[kk][i] as:
        max from prev=0 to prev = i-1 of (dp[kk-1][prev] + (p[i] - p[prev]) * (p.back() - p[i]))

        now at each kk we define a family of functions f_prev(u) like so:
            f_prev(u) = dp[kk-1][prev] + p[prev]*u

        then we can rewrite:
            dp[kk][i] = (max from family(p[i] - p[back])) + (p[i]*p.back() - p[i]^2)

        note that for each prev, we have a linear function f_prev
    */
    std::vector<std::vector<long long>> dp(k+2, std::vector<long long>(n+1));
    std::vector<std::vector<int>> bestfrom(k+2, std::vector<int>(n+1));
    /*
        when kk=0, it must be that we can get no score
    */
    for (int i = 0; i <= n; ++i) dp[0][i] = 0;
    /*
        when i = 0 but kk > 0 then we cannot even do anything, not even score 0
    */
    for (int kk = 1; kk <= k+1; ++kk) dp[kk][0] = -INF;
    for (int kk = 1; kk <= k+1; ++kk) {
        ConvexHull hull;
        hull.emplace(p[0], dp[kk-1][0]);
        for (int i = 1; i <= n; ++i) {
            dp[kk][i] = hull.querymax(p[i] - p.back(), &bestfrom[kk][i]) + p[i] * (p.back() - p[i]);
            hull.emplace(p[i], dp[kk-1][i]);
        }
    }
    std::cout << dp[k+1][n] << '\n';
    int cur = bestfrom[k+1][n];
    while (k) {
        std::cout << cur << " \n"[k==1];
        cur = bestfrom[k][cur];
        --k;
    }
}

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