제출 #1336849

#제출 시각아이디문제언어결과실행 시간메모리
1336849al95ireyizKpart (eJOI21_kpart)C++20
30 / 100
2025 ms685464 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define len(x) (ll)x.size()
const ll inf = 1e9, infl = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 1e5 + 5;
ll n, m, k = 0;

ll a[maxn], pref[maxn], dp[1005][maxn];
void _() {
  cin >> n;
  for(ll i = 1; i <= n; i ++){
    cin >> a[i];
    pref[i] = pref[i - 1] + a[i];
  }

  // qisacasi ele x-leri tapmaliyiq ki her bir valid [l, r](x = r - l + 1) ucun [l, r] araliginda
  // (pref[r] - pref[l - 1]) / 2 cemini yaradan ededler olsun

  for(ll cm = 0; cm < maxn; cm ++){
    dp[0][cm] = -inf;
  }
  for(ll r = 1; r <= n; r ++){
    for(ll cm = 1; cm < maxn; cm ++){
      dp[r][cm] = dp[r - 1][cm];

      if(cm == a[r]) dp[r][cm] = r;

      else if(cm > a[r]) dp[r][cm] = max(dp[r][cm], dp[r - 1][cm - a[r]]);
    }
  }

  vll v;
  for(ll x = 1; x <= n; x ++){
    bool ok = 1;
    for(ll l = 1, r = x; r <= n; l ++, r ++){
      ll cm = pref[r] - pref[l - 1], tr = cm / 2;
      if(cm % 2 or dp[r][tr] < l){
        ok = 0;
        break;
      }
    }
    if(ok) v.push_back(x);
  }
  cout << len(v) << ' ';
  for(auto x : v) cout << x << ' ';
  cout << '\n';
}
signed main() {
  cin.tie(0)->sync_with_stdio(0);
  ll t = 1;
  cin >> t;
  while(t --) _();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...