Submission #923538

#TimeUsernameProblemLanguageResultExecution timeMemory
923538KiaRezKpart (eJOI21_kpart)C++17
100 / 100
779 ms3060 KiB
/* IN THE NAME OF GOD */ #include <bits/stdc++.h> // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef long double ld; #define F first #define S second #define Mp make_pair #define pb push_back #define pf push_front #define size(x) ((ll)x.size()) #define all(x) (x).begin(),(x).end() #define kill(x) cout << x << '\n', exit(0); #define fuck(x) cout << "(" << #x << " , " << x << ")" << endl #define endl '\n' const int N = 3e5+23, lg = 18; ll Mod = 1e9+7; //998244353; inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;} inline ll poww(ll a, ll b, ll mod=Mod) { ll ans = 1; a=MOD(a, mod); while (b) { if (b & 1) ans = MOD(ans*a, mod); b >>= 1; a = MOD(a*a, mod); } return ans; } int n, t, a[N], dp[N], cnt[N]; void solve() { vector<int> ans; int sum = 0; cin>>n; fill(dp, dp+N, 0); fill(cnt, cnt+N, 0); dp[0] = n+1; for(int i=1; i<=n; i++) { cin>>a[i]; sum += a[i]; for(int j=sum; j>=a[i]; j--) { dp[j] = max(dp[j], min(i, dp[j-a[i]])); } int sum2 = 0; for(int j=i; j>=1; j--) { sum2 += a[j]; if(sum2%2==0 && dp[sum2/2] >= j) { cnt[i-j+1] ++; } } } for(int i=1; i<=n; i++) if(cnt[i] == n-i+1) ans.pb(i); cout<<size(ans)<<' '; for(auto it : ans) cout<<it<<' '; cout<<endl; } int main () { ios_base::sync_with_stdio(false), cin.tie(0); 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...