Submission #446186

#	Time	Username	Problem	Language	Result	Execution time	Memory
446186		nishuz	Split the sequence (APIO14_sequence)	C++17	100 / 100	1443 ms	81840 KiB

sequence

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define mp make_pair
#define random mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
 
template <typename T> using oset = tree <pair <T, T>, null_type, less <pair <T, T>>, rb_tree_tag, tree_order_statistics_node_update>;
 
template <typename Container>
void Print(Container& container, int starting) {
    auto Start = container.begin() + starting, End = container.end();
    while (Start != End) cout << *(Start++) << " ";
    cout << '\n';
}
 
template <typename T>
void print(T&& t) {cout << t << '\n';}
 
template <typename T, typename... Args>
void print(T&& t, Args&&... args) {
    cout << t << " ";
    print(forward<Args>(args)...);
}

const int32_t MAXN = 1e5 + 5, MAXK = 205;
int64_t a[MAXN], dp[2][MAXN], n;
int32_t par[MAXK][MAXN];

void compute(int32_t l, int32_t r, int32_t optl, int32_t optr, int32_t k)
{
    if (l > r) return;
    int32_t mid = (l + r) >> 1, row = k & 1;
    pair <int64_t, int64_t> best = make_pair(-1, -1);
    for (int64_t i = optl; i < min(mid, optr + 1); ++i) best = max(best, make_pair(dp[row ^ 1][i] + (a[n] - a[mid]) * (a[mid] - a[i]), i));
    dp[row][mid] = best.first;
    par[k][mid] = best.second;
    int64_t opt = best.second;
    compute(l, mid - 1, optl, opt, k);
    compute(mid + 1, r, opt, optr, k);
}

inline void solve() {
    int32_t k;
    cin >> n >> k;
    memset(a, 0, sizeof a);
    for (int32_t i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    for (int32_t i = 0; i <= k; ++i) {
        for (int32_t j = 0; j <= n; ++j) {
            par[i][j] = -1;
        }
    }
    for (int32_t i = 0; i <= n; ++i) {
        dp[0][i] = dp[1][i] = -1;
    }
    dp[0][0] = 0;
    for (int32_t i = 1; i <= k; ++i) {
        compute(0, n - 1, 0, n - 1, i);
    }
    pair <int64_t, int32_t> ans = mp(-1, -1);
    for (int32_t i = 1; i <= n; ++i) {
        ans = max(ans, mp(dp[k & 1][i], i));
    }
    print(ans.F);
    vector <int32_t> seq(k + 1);
    int32_t cur = k;
    while (k && ans.S != -1) {
        seq[cur--] = ans.S;
        assert(ans.S >= 1 && ans.S <= n);
        ans.S = par[k--][ans.S];
    }
    Print(seq, 1);
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int test = 1; test <= T; ++test) {
        // cout << "Case #" << test << ": ";
        solve();
    }
}

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