Submission #987669

#	Time	Username	Problem	Language	Result	Execution time	Memory
987669		JahonaliX	Split the sequence (APIO14_sequence)	C++17	0 / 100	2068 ms	1116 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    int n, k, mx = 0, sm;
    cin >> n >> k;
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (i) a[i] += a[i - 1];
    }
    vector<int> ans, vec;
    for (int i = 1; i <= k; ++i) vec.emplace_back(i);
    while (true) {
        sm = 0;
        for (int i = 0; i < k; ++i) {
            if (i) sm += (a[vec[i] - 1] - a[vec[i - 1] - 1]) * (a[n - 1] - a[vec[i] - 1]);
            else sm += a[vec[i] - 1] * (a[n - 1] - a[vec[i] - 1]);
        }
        if (sm > mx) ans = vec, mx = sm;
        vec[k - 1]++;
        for (int i = k - 1; i > 0; --i) if (vec[i] > n - k + i + 1) vec[i - 1]++, vec[i] = i + 1;
        if (vec[0] > n - k + 1) break;
    }
    cout << mx << '\n';
    for (int i : ans) cout << i << ' ';
    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