Submission #1300737

#TimeUsernameProblemLanguageResultExecution timeMemory
1300737gsalterKpart (eJOI21_kpart)C++20
100 / 100
1128 ms195992 KiB
#include "bits/stdc++.h" using namespace std; #define maxN 1005 #define maxS 50005 int a[maxN]; int prefix[maxS]; int dp[maxN][maxS]; int n; void helper() { cin >> n; for (int i=1; i<=n; i++) cin >> a[i]; for (int i=0; i<=n; i++) fill(dp[i], dp[i]+maxN-1, 0); for (int i=1; i<=n; i++) prefix[i] = prefix[i-1] + a[i]; for (int r=1; r<=n; r++) { for (int s=0; s<=maxS-5; s++) { dp[r][s] = dp[r-1][s]; if (s==a[r]) dp[r][s] = r; if (s>a[r]) dp[r][s] = max(dp[r][s], dp[r-1][s-a[r]]); } } vector<int> ans; for (int k=2; k<=n; k++) { bool ok = 1; for (int r=k; r<=n; r++) { int l = r-k+1; int sum = prefix[r] - prefix[l-1]; if (sum&1) ok = 0; if (dp[r][sum/2] < l) ok = 0; } if (ok) ans.push_back(k); } cout << ans.size() << " "; for (int x: ans) cout << x << " "; cout << endl; } int main() { int t; cin >> t; while (t--) helper(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...