Submission #1013678

#TimeUsernameProblemLanguageResultExecution timeMemory
1013678_fractalKpart (eJOI21_kpart)C++14
0 / 100
407 ms100692 KiB
#include <bits/stdc++.h> using namespace std; #define F first #define S second #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end()) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 1e3 + 20; const int M = 1e5 + 20; const int inf = 2e9 + 3; const ll INF = 1e18; int n; int a[N]; int dp[N][M], is[N]; void solve() { cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; for (int j = 0; j < M; ++j) dp[i][j] = 0; for (int j = a[i]; j < M; ++j) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]); dp[i][0] = i; dp[i][a[i]] = i; is[i] = 1; } for (int i = 1; i <= n; ++i) { for (int j = i, sum = 0; j <= n; ++j) { sum += a[j]; if (sum % 2 == 1 || dp[j][sum / 2] < i) is[j - i + 1] = 0; } } cout << accumulate(is + 1, is + n + 1, 0) << '\n'; for (int i = 1; i <= n; ++i) if (is[i]) cout << i << " "; cout << '\n'; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...