Submission #367840

#	Time	Username	Problem	Language	Result	Execution time	Memory
367840		valerikk	Split the sequence (APIO14_sequence)	C++17	17 / 100	2076 ms	8684 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll slow(int n, int k, vector<ll> a, vector<int> &c) {
    vector<ll> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + a[i];
    
    auto cost = [&](int l, int r)->ll {
        return (pref[r] - pref[l]) * (pref[r] - pref[l]);
    };

    vector<vector<int>> opt(k + 1, vector<int>(n, -1));
    vector<ll> dp(n + 1);
    for (int i = 0; i <= n; i++) dp[i] = cost(0, i);
    for (int t = 1; t <= k; t++) {
        vector<ll> ndp(n + 1, INF);
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < i; j++) { 
                if (dp[j] + cost(j, i) < ndp[i]) ndp[i] = dp[j] + cost(j, i), opt[t][i] = j;
            }
        }
        dp.swap(ndp);
    }

    ll res = (cost(0, n) - dp[n]) / 2;

    int cur = n;
    for (int i = k; i >= 0; i--) {
        if (i != k) c.push_back(cur);
        cur = opt[i][cur];
    }
    reverse(c.begin(), c.end());

    return res;
}

ll fast(int n, int k, vector<ll> a, vector<int> &c) {
    return 0;
}

int main() {
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll &x : a) cin >> x;
    assert(k + 1 <= n);
    vector<int> c;
    if (1) cout << slow(n, k, a, c); else cout << fast(n, k, a, c);
    cout << endl;
    for (int i : c) cout << i << " ";
    cout << endl;
    return 0;
}

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