제출 #1337438

#제출 시각아이디문제언어결과실행 시간메모리
1337438ayazKpart (eJOI21_kpart)C++20
100 / 100
1711 ms391504 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algos/debug.h"
#else
#define debug(...) 42;
#endif

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)x.size()

const int sz = 1e3 + 10;
const int mx = 1e5 + 10;

int a[sz], p[sz];
int dp[sz][mx];

void run(int tc) {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p[i] = p[i - 1] + a[i];
  }
  int sm = p[n];
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= sm; w++) {
      if (w == a[i]) {
        dp[i][w] = i;
        continue;
      }
      if (w > a[i]) {
        dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - a[i]]);
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  debug(dp[2][5]);
  vector<int> ans;
  for (int k = 2; k <= n; k++) {
    bool ok = true;
    for (int l = 1; l <= n - k + 1; l++) {
      int r = l + k - 1;
      int sm = p[r] - p[l - 1];
      debug(k, l, r, sm);
      if (sm % 2 || dp[r][sm / 2] < l) {
        ok = false;
        break;
      }
    }
    if (ok) ans.push_back(k);
  }
  cout << ans.size() << ' ';
  for (auto &i : ans) {
    cout << i << ' ';
  }
  cout << '\n';
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);  
  int t = 1;
  cin >> t;
  for (int tc = 1; tc <= t; tc++) run(tc);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...