Submission #1106405

#TimeUsernameProblemLanguageResultExecution timeMemory
1106405MuhammetKpart (eJOI21_kpart)C++17
100 / 100
1794 ms1228 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define ff first #define ss second const int N = 3e5+5; int T, n; int main(){ cin >> T; while(T--){ cin >> n; vector <int> a(n+1); int s1 = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; s1 += a[i]; } vector <bool> vis(n+1,0); vector <int> dp(s1+1,0), dp1(s1+1,0); for(int i = 1; i <= n; i++){ dp1[a[i]] = i; for(int j = a[i]; j <= s1; j++){ dp1[j] = max(dp1[j], dp[j - a[i]]); } int s = 0; // cout << i << "\n"; for(int j = i; j >= 1; j--){ s += a[j]; // cout << j << " " << s << ' ' << dp[s/2] << "\n"; if(dp[s/2] < j or s % 2 == 1) vis[i-j+1] = 1; } dp = dp1; } vector <int> v; int cnt = 0; for(int i = 1; i <= n; i++){ if(vis[i] == 0){ cnt++; v.push_back(i); } } cout << cnt << ' '; for(auto i : v){ cout << i << " "; } cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...