Submission #1230357

#TimeUsernameProblemLanguageResultExecution timeMemory
1230357dibamboo23Kpart (eJOI21_kpart)C++20
0 / 100
124 ms992 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[e5+3]; bool res[N]; int p[N]; int a[1003]; void code(){ int n;cin>>n; for(int i=2;i<=n;i++)res[i]=1; for(int j=1;j<=e5;j++)dp[j]=0; int k=e5/2; for(int i=1;i<=n;i++){ cin>>a[i]; p[i]=p[i-1]+a[i]; dp[a[i]]=i; for(int j=k;j>a[i];j--){ dp[j]=max({dp[j-a[i]],dp[j]}); } 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...