Submission #520416

#	Time	Username	Problem	Language	Result	Execution time	Memory
520416		Alex_tz307	Kpart (eJOI21_kpart)	C++17	100 / 100	834 ms	600 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int kN = 1e3;
const int kS = 5e4;
int a[1 + kN], last[1 + kS], cnt[1 + kN];

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void testCase() {
  int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sum += a[i];
    cnt[i] = 0;
  }
  sum /= 2;
  for (int s = 0; s <= sum; ++s) {
    last[s] = 0;
  }
  for (int i = 1; i <= n; ++i) {
    for (int s = sum; s > a[i]; --s) {
      maxSelf(last[s], last[s - a[i]]);
    }
    last[a[i]] = i;
    int s = 0;
    for (int j = i; j > 0; --j) {
      s += a[j];
      if (s % 2 == 0 && j <= last[s / 2]) {
        ++cnt[i - j + 1];
      }
    }
  }
  int total = 0;
  for (int i = 1; i <= n; ++i) {
    if (cnt[i] == n - i + 1) {
      ++total;
    }
  }
  cout << total << ' ';
  for (int i = 1; i <= n; ++i) {
    if (cnt[i] == n - i + 1) {
      cout << i << ' ';
    }
  }
  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests;
  cin >> tests;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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