Submission #1089159

#TimeUsernameProblemLanguageResultExecution timeMemory
1089159vjudge1Kpart (eJOI21_kpart)C++17
0 / 100
1142 ms2616 KiB
//don't copy pls) /*TAAK ZDES NADO RECURSIU PISAT*/ //I'm not in the danger i am the DANGER #include "bits/stdc++.h" #include <ext/pb_ds/assoc_container.hpp> #define ll long long #define pb push_back #define int long long #define F first #define S second #define all(x) (x).begin(), (x).end() #define pii pair<int,int> #define sigma signed using namespace std; using namespace __gnu_pbds; const int N = 1e5 + 5; int mod = 1e9 + 7; const int INF = 1e18; int n,a[N],p[N],dp[121][N]; void Gold(){ cin >> n; for(int i = 1 ; i <= n ; i++){ cin >> a[i]; p[i] = p[i - 1] + a[i]; } vector <int> ans; for(int k = 2 ; k <= n ; k++){ bool ok = 1; for(int i = k ; i <= n ; i++){ int sum = p[i] - p[i - k]; if(sum % 2){ ok = 0; break; } sum /= 2; for(int j = 1 ; j <= n ; j++){ dp[j][0] = 1; for(int x = 1 ; x <= sum ; x++){ dp[j][x] = 0; } } for(int j = 1 ; j <= n ; j++){ for(int x = 1 ; x <= sum ; x++){ dp[j][x] = max(dp[j - 1][x] , dp[j][x]); if(x >= a[j]){ dp[j][x] = max(dp[j][x] , dp[j - 1][x - a[j]]); } } } bool okok = 0; for(int j = 1 ; j <= n ; j++){ if(dp[j][sum]){ okok = 1; break; } } if(!okok){ ok = 0; break; } } if(ok){ ans.pb(k); } } cout << ans.size() << ' '; for(auto it : ans){ cout << it << ' '; } cout << '\n'; } sigma main(){ //freopen("txt.in","r",stdin); //freopen("txt.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); srand(time(0)); int TT = 1; cin >> TT; for(int i = 1 ; i <= TT ; i++){ //cout << "Case " << i << ": "; Gold(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...