Submission #1254158

#TimeUsernameProblemLanguageResultExecution timeMemory
1254158smartmonkyKpart (eJOI21_kpart)C++20
100 / 100
1788 ms676 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") const int N = 1e3 + 5; const int S = 1e5 + 1; int a[N], p[N], ok[N]; uint16_t dp[S]; void solve() { int n, M = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; M += a[i]; p[i] = p[i - 1] + a[i]; } fill(dp, dp + M + 1, N); dp[0] = n + 1; for (int i = n; i >= 1; i--) { dp[0] = i; for (int j = M; j >= a[i]; j--) { if (dp[j - a[i]] < dp[j]) { dp[j] = dp[j - a[i]]; } if (!(j & 1) && dp[j >> 1] <= dp[j] && (p[dp[j]] - p[i - 1]) == j) { ok[dp[j] - i + 1]++; } } } int cnt = 0; for (int i = 1; i <= n; i++) { cnt += (ok[i] == n - i + 1); } cout << cnt << " "; for (int i = 1; i <= n; i++) { if (ok[i] == n - i + 1) { cout << i << " "; } ok[i] = 0; } cout << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...