oj.uz

Submission #520416

# Submission time Handle Problem Language Result Execution time Memory
520416 2022-01-29T21:59:41 Z Alex_tz307 Kpart (eJOI21_kpart) C++17
100 / 100
 834 ms 600 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 332 KB Output is correct
2 Correct 24 ms 352 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 376 KB Output is correct
2 Correct 168 ms 428 KB Output is correct
3 Correct 176 ms 448 KB Output is correct
4 Correct 299 ms 456 KB Output is correct
5 Correct 605 ms 564 KB Output is correct
6 Correct 834 ms 600 KB Output is correct
7 Correct 826 ms 584 KB Output is correct