Submission #1267960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267960		madamadam3	Split the sequence (APIO14_sequence)	C++20	11 / 100	2087 ms	436 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define int long long int
using vi = vector<int>;
using vvi = vector<vi>;

int score(int n, int k, vi &order, vi &prefix) {
    set<int> used; used.insert(0); used.insert(n);
    int ans = 0;

    for (int i = 0; i < k; i++) {
        auto it1 = used.lower_bound(order[i]);
        int L = *prev(it1), R = *it1;

        ans += (prefix[order[i]] - prefix[L]) * (prefix[R] - prefix[order[i]]);
        used.insert(order[i]);
    }

    return ans;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, k; cin >> n >> k;
    vi a(n); for (int i = 0; i < n; i++) cin >> a[i];
    vi prefix(n+1, 0); for (int i = 0; i < n; i++) prefix[i+1] += a[i] + prefix[i];
    
    vi best(n-1); iota(best.begin(), best.end(), 1); vi cur = best;
    int best_score = score(n, k, best, prefix); int cur_score = best_score;

    do {
        int s = score(n, k, cur, prefix);
        if (s > best_score) {
            best_score = s; best = cur;
        }
    } while (next_permutation(cur.begin(), cur.end()));

    cout << best_score << "\n";
    for (int i = 0; i < k; i++) cout << best[i] << " ";
    cout << "\n";
    return 0;
}

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