# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
582672 |
2022-06-24T08:43:33 Z |
tengiz05 |
Kpart (eJOI21_kpart) |
C++17 |
|
1254 ms |
724 KB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 50005;
void solve() {
int n;
cin >> n;
vector<int> a(n), pre(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
pre[i + 1] = pre[i] + a[i];
}
vector<int> dp(N + 1, -1);
dp[0] = 0;
vector<bool> ans(n, true);
for (int i = 0; i < n; i++) {
for (int j = N; j >= a[i]; j--) {
dp[j] = max(dp[j], dp[j - a[i]]);
}
dp[a[i]] = i;
for (int j = 0; j <= i; j++) {
int sum = pre[i + 1] - pre[j];
if (sum % 2 != 0 || dp[sum / 2] < j) {
ans[i - j] = false;
}
}
}
vector<int> res;
for (int i = 0; i < n; i++) {
if (ans[i])
res.push_back(i + 1);
}
cout << res.size() << " ";
for (int x : res) {
cout << x << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
500 KB |
Output is correct |
2 |
Correct |
141 ms |
528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
286 ms |
504 KB |
Output is correct |
2 |
Correct |
468 ms |
528 KB |
Output is correct |
3 |
Correct |
477 ms |
500 KB |
Output is correct |
4 |
Correct |
681 ms |
516 KB |
Output is correct |
5 |
Correct |
1000 ms |
540 KB |
Output is correct |
6 |
Correct |
1254 ms |
656 KB |
Output is correct |
7 |
Correct |
1155 ms |
536 KB |
Output is correct |