Submission #987670

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
987670	2024-05-23T10:34:12 Z	JahonaliX	Split the sequence (APIO14_sequence)	C++17	0 / 100	2000 ms	600 KB

sequence

#include <bits/stdc++.h>

using namespace std;

int 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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	contestant found the optimal answer: 108 == 108
2	Correct	1 ms	348 KB	contestant found the optimal answer: 999 == 999
3	Incorrect	1 ms	348 KB	Unexpected end of file - int32 expected
4	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	348 KB	contestant found the optimal answer: 1093956 == 1093956
2	Correct	2 ms	348 KB	contestant found the optimal answer: 302460000 == 302460000
3	Execution timed out	2097 ms	344 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	348 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	52 ms	348 KB	contestant found the optimal answer: 311760000 == 311760000
3	Execution timed out	2017 ms	344 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-