Submission #1267965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267965		madamadam3	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	324 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 base(n-1); iota(base.begin(), base.end(), 1);
    int base_score = score(n, n-1, base, prefix);

    while (base.size() > k) {
        vi nw; int nscore = -1;
        
        for (auto el : base) {
            vi nbase; for (auto &i : base) if (i != el) nbase.push_back(i);
            int ns = score(n, nbase.size(), nbase, prefix);

            if (ns > nscore) nw = nbase, nscore = ns;
        }

        base = nw; base_score = nscore;
    }

    cout << base_score << "\n";
    for (auto &el : base) cout << el << " "; cout << "\n";
    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