Submission #973347

#	Time	Username	Problem	Language	Result	Execution time	Memory
973347		avighna	Split the sequence (APIO14_sequence)	C++17	50 / 100	2041 ms	61112 KiB

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;

class Ans {
public:
    ll tot;
    ll cur;
    ll idx;
};

bool operator<(const Ans &a, const Ans &b) {
    return a.tot < b.tot;
}

Ans dp[N][K];

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 = n - 1; i >= 0; -- i) {
        for (ll j = 0; j <= k; ++ j) {
            if (i == n - 1) {
                if (j != 0) {
                    dp[i][j].tot = -inf;
                } else {
                    dp[i][j].tot = 0;
                }
                continue;
            }
            if (j == 0) {
                dp[i][j].tot = 0;
                continue;
            }

            dp[i][j].tot = 0;
            for (ll c = i; c < n - 1; c++) {
                ll cur = a.sum(i, c) * a.sum(c + 1, n - 1);
                dp[i][j] = std::max(dp[i][j], {cur + dp[c + 1][j - 1].tot, cur, c + 1});
            }
        }
    }

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

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