Submission #1171422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171422		fryingduc	Kpart (eJOI21_kpart)	C++20	100 / 100	576 ms	748 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1005;
const int N = 5e4 + 5;
int n, a[maxn];
int f[N], prf[maxn];
bool ban[maxn];

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    prf[i] = prf[i - 1] + a[i];
  }
  memset(ban, 0, sizeof(ban));
  memset(f, 0, sizeof(f));
  for (int i = 1; i <= n; ++i) {
    for (int j = N - 1; j >= a[i]; --j) {
      f[j] = max(f[j], f[j - a[i]]);
    }
    f[a[i]] = i;
    for (int k = 2; k <= i; ++k) {
      if ((prf[i] - prf[i - k]) & 1 || f[(prf[i] - prf[i - k]) / 2] <= i - k) {
        ban[k] = 1;
      }
    }
  }
  vector<int> cand;
  for (int i = 2; i <= n; ++i) {
    if (!ban[i]) cand.push_back(i);
  }
  cout << (int)cand.size() << " ";
  for (auto i : cand) cout << i << " ";
  cout << '\n';
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int tt; cin >> tt;
  while (tt--) {
    solve();
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70