제출 #1318324

#제출 시각아이디문제언어결과실행 시간메모리
1318324jesusargKpart (eJOI21_kpart)C++20
30 / 100
1101 ms167228 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; int dp[1001][50002]; int32_t main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; vector<int> v(n),pref(n+1,0); int tot=0; for(auto&i:v)cin>>i,tot+=i; for(int i = 0; i <= n; i++){ for(int j = 0; j <= ceil(tot/2); j++){ dp[i][j]=-1; } } for(int i = 0; i < n; i++){ pref[i+1]=pref[i]+v[i]; dp[i+1][v[i]]=i+1; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= pref[i]; j++){ dp[i][j]=max({dp[i][j],dp[i-1][j]}); if(v[i-1]<j){ dp[i][j] = max(dp[i][j], dp[i-1][j-v[i-1]]); } } } vector<int> ans; for(int i = 2; i <= n; i++){ bool ok=1; for(int j = i; j <= n; j++){ int sum=pref[j]-pref[j-i]; if(sum&1){ ok=0;break; } if(dp[j][sum/2] < (j-i+1)){ ok=0;break; } } if(ok) ans.pb(i); } cout << ans.size() << ' '; for(auto i : ans) cout << i << ' '; cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...