Submission #476681

#	Time	Username	Problem	Language	Result	Execution time	Memory
476681		Shin	Split the sequence (APIO14_sequence)	C++14	0 / 100	2099 ms	54252 KiB

sequence

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define all(x) x.begin(), x.end()

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}
int n, k;
int pre[N];
vector<int> res;
map<int, ll> dp[N];
map<int, int> trace[N];

ll compute(int l, int r, int level) {
    if (level >= k || l >= r) return 0LL;
    
    ll res = dp[l][r];
    if (res) return res;

    for (int i = l; i < r; i ++) {
        ll tmp = 1LL * (pre[i] - pre[l - 1]) * (pre[r] - pre[i]);
        if (maximize(res, compute(l, i, level + 1) + compute(i + 1, r, level + 1) + tmp))
            trace[l][r] = i;
    }
    return dp[l][r] = res;
}

void retrace(int l, int r, int level) {
    if (l >= r || level >= k) return;
    int m = trace[l][r];
    res.push_back(m);
    retrace(l, m, level + 1);
    retrace(m + 1, r, level + 1);
}

void solve(void) {
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) {
        int x; cin >> x;
        pre[i] = pre[i - 1] + x;
    }
    cout << compute(1, n, 1) << '\n';
    retrace(1, n, 1);
    for (int x: res) cout << x << " ";
}

int main(void) {
    cin.tie(0)->sync_with_stdio(0); 
    int test = 1;
    // cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

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