Submission #1230365

#TimeUsernameProblemLanguageResultExecution timeMemory
1230365dibamboo23Kpart (eJOI21_kpart)C++20
100 / 100
582 ms708 KiB
#include <bits/stdc++.h> #define ll long long #define F first #define S second #define sz size() using namespace std; [[maybe_unused]]const int e5=1e5; [[maybe_unused]]const int e6=1e6; [[maybe_unused]]const int e7=1e7; [[maybe_unused]]const int e8=1e8; [[maybe_unused]]const int e9=1e9; inline int rd(){ int num;cin>>num; return num; } inline ll rdll(){ ll num;cin>>num; return num; } [[maybe_unused]]const ll inf=1e18+7; [[maybe_unused]]const ll MOD=1e9+7; [[maybe_unused]]const int N=1e6+3; int dp[N]; bool res[N]; int p[N]; int a[N]; void code(){ int n;cin>>n; for(int i=2;i<=n;i++)res[i]=1; int k=e5/2; for(int j=1;j<=k;j++)dp[j]=0; for(int i=1;i<=n;i++){ cin>>a[i]; p[i]=p[i-1]+a[i]; for(int j=k;j>=a[i];j--){ dp[j]=max(dp[j-a[i]],dp[j]); } if(a[i]<=k)dp[a[i]]=i; for(int j=2;j<=i;j++){ int l=i-j+1; if(((p[i]-p[l-1])&1)==1||dp[(p[i]-p[l-1])/2]<l)res[j]=0; } } vector<int>ress; for(int i=1;i<=n;i++){ if(res[i])ress.push_back(i); } cout<<(int)ress.sz<<" "; for(auto to:ress)cout<<to<<" "; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int tt=1; cin>>tt; while(tt--)code(),cout<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...