Submission #973379

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
973379	2024-05-01T21:24:22 Z	avighna	Split the sequence (APIO14_sequence)	C++17	0 / 100	45 ms	101460 KB

sequence

#include <bits/stdc++.h>

typedef long long ll;

template <typename T> class Vector : public std::vector<T> {
public:
    using std::vector<T>::vector;
    std::vector<ll> psum;

    void calculate_prefix_sum() {
        psum.resize(this->size());
        std::partial_sum(this->begin(), this->end(), psum.begin());
    }

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

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

ll dp[K][N];

struct Line {
    ll m, b;

    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.front()) && l.b <= dq.front().b) {
            return;
        }
        while (dq.size() >= 2) {
            if (parallel(l, dq.front())) {
                if (l.b > dq.front().b) {
                    dq.pop_front();
                    continue;
                } else {
                    return;
                }
            }
            if (x_intersection(l, dq[0]) >= x_intersection(dq[0], dq[1])) {
                dq.pop_back();
            } else {
                break;
            }
        }
        if (dq.size() == 1 && parallel(l, dq.front()) && l.b > dq.front().b) {
            dq.pop_front();
        }
        dq.push_front(l);
    }

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

int main() {
    ll n, k;
    std::cin >> n >> k;
    Vector<ll> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }
    a.calculate_prefix_sum();

    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) {
                if (i != 0) {
                    dp[i][j] = -inf;
                } else {
                    dp[i][j] = 0;
                }
                continue;
            }
            if (i == 0) {
                dp[i][j] = 0;
                continue;
            }

            dp[i][j] = 0;
            ll m = a.sum(j + 1, n - 1);
            ll b = dp[i - 1][j + 1] + a.sum(0, j) * a.sum(j + 1, n - 1);
            hull.insert({m, b});
            dp[i][j] = std::max(0LL, hull.query(-a.sum(0, j - 1)));
        }
    }

    std::cout << dp[k][0] << "\n";
    ll i = 0;
    ll ops = k;
    for (ll c = i; c < n - 1 && ops > 0; c++) {
        if (dp[ops][i] == a.sum(i, c) * a.sum(c + 1, n - 1) + dp[ops - 1][c + 1]) {
            std::cout << c + 1 << " ";
            ops--;
            i = c + 1;
        }
    }
}

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4440 KB	contestant found the optimal answer: 108 == 108
2	Incorrect	1 ms	2396 KB	contestant didn't find the optimal answer: 774 < 999
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4444 KB	contestant didn't find the optimal answer: 1091946 < 1093956
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4444 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	1 ms	4444 KB	contestant found the optimal answer: 311760000 == 311760000
3	Correct	45 ms	101460 KB	contestant found the optimal answer: 1989216017013 == 1989216017013
4	Incorrect	1 ms	4444 KB	contestant didn't find the optimal answer: 136647055110 < 1499437552673
5	Halted	0 ms	0 KB	-