Submission #1254167

#TimeUsernameProblemLanguageResultExecution timeMemory
1254167smartmonkyKpart (eJOI21_kpart)C++20
30 / 100
2093 ms872 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define ll long long using namespace std; const int N = 1e3 + 5, S = 1e5 + 1; int dp[S], a[N],p[N],ok[N]; 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]; } for(int i = 1;i <= M; i++) dp[i] = 1e5; for(int i = n; i >= 1; i--){ dp[0] = i; for(int j = M; j>= 1; j--){ if(j >= a[i]) dp[j] = min(dp[j],dp[j - a[i]]); if( j % 2 == 0 && dp[j / 2] <= dp[j] && (p[dp[j]] - p[i - 1]) == j) ok[dp[j] - i + 1] ++; } } int cnt = 0; for(int i = 1; i <= n ; i++){ if(ok[i] == n - i + 1) cnt++; } cout<<cnt <<" "; for(int i = 1; i <= n ; i++){ if(ok[i] == n - i + 1) cout <<i <<" "; ok[i] = 0; p[i] = 0; } cout<<endl; for(int i = 1;i <= M; i++) dp[i] = 0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...