Submission #1295939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295939		idk_anything_i_guess	수열 (APIO14_sequence)	C++20	33 / 100	3 ms	2624 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<ll> a(n+1), prefix(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        prefix[i] = prefix[i-1] + a[i];
    }

    // dp[i][j] = max points with i splits in first j elements
    vector<vector<ll>> dp(k+1, vector<ll>(n+1, 0));
    // opt[i][j] = position t of last split
    vector<vector<int>> opt(k+1, vector<int>(n+1, 0));

    for (int i = 1; i <= k; i++) {
        int t = 0; // pointer to track optimal previous split
        for (int j = 1; j <= n; j++) {
            // Move t to the right while it improves dp[i][j]
            while (t < j-1) {
                ll curr = dp[i-1][t] + prefix[t]*(prefix[j]-prefix[t]);
                ll next = dp[i-1][t+1] + prefix[t+1]*(prefix[j]-prefix[t+1]);
                if (next >= curr) t++;
                else break;
            }
            dp[i][j] = dp[i-1][t] + prefix[t]*(prefix[j]-prefix[t]);
            opt[i][j] = t;
        }
    }

    // Reconstruct split positions
    vector<int> splits;
    int curr_j = n;
    int curr_i = k;
    while (curr_i > 0) {
        int t = opt[curr_i][curr_j];
        splits.push_back(t);
        curr_j = t;
        curr_i--;
    }
    reverse(splits.begin(), splits.end());

    cout << dp[k][n] << "\n";
    for (int s : splits) cout << s << " ";
    cout << "\n";

    return 0;
}

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