제출 #582543

#제출 시각아이디문제언어결과실행 시간메모리
582543talant117408Kpart (eJOI21_kpart)C++17
0 / 100
13 ms1888 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define long unsigned long #define pb push_back #define mp make_pair #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define lb lower_bound #define ub upper_bound #define sz(v) int((v).size()) #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl '\n' #define PI 2*acos(0.0) void solve() { int n; cin >> n; vector <int> v(n+1), pref(n+1); for (int i = 1; i <= n; i++) { cin >> v[i]; pref[i] = pref[i-1] + v[i]; } bitset <1001> ans; for (int i = 1; i <= n; i++) ans[i] = 1; vector <bitset <50001>> dp(n+1); dp[0][0] = 1; for (int i = 1; i <= n; i++) { dp[i] = (dp[i-1] | (dp[i-1] << v[i])); for (int j = i; j >= 1; j--) { if ((pref[i]-pref[j-1])&1) { ans[i-j+1] = 0; } //~ else if ((pref[i]-pref[j-1])/2 > pref[j-1]) { //~ ans[i-j+1] = 0; //~ cout << 1 << ' ' << j << ' ' << i << endl; //~ } else if (dp[i][pref[i]-(pref[i]-pref[j-1])/2] == 0) { ans[i-j+1] = 0; } } } vector <int> K; for (int i = 2; i <= n; i++) { if (ans[i]) K.pb(i); } cout << sz(K) << ' '; for (auto to : K) cout << to << ' '; cout << endl; } int main() { do_not_disturb int t = 1; 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...