Submission #1253684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253684		matthew	Kpart (eJOI21_kpart)	C++20	100 / 100	442 ms	636 KiB

Main

#include <stdio.h>
#include <algorithm>
using ll = long long;

const int MAX_N = 1'000;
const int MAX_SUM = 50'000;
const int INF = 1e9;

int a[MAX_N];
ll sp[MAX_N + 1];
int dp[MAX_SUM + 1];
bool ok[MAX_N + 1];

void add(int pos) {
  int val = a[pos];
  if(val > MAX_SUM) return;
  for(int i = MAX_SUM; i > val; i--) {
    dp[i] = std::max(dp[i], dp[i - val]);
  }
  dp[val] = pos;
}

bool possible(int l, int r) {
  ll sum = sp[r + 1] - sp[l];
  if(sum % 2 == 1) return false;
  return dp[sum / 2] >= l;
}

void solve_test() {
  int n;
  scanf("%d", &n);
  for(int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    sp[i + 1] = sp[i] + a[i];
  }

  dp[0] = INF;
  for(int i = 1; i <= MAX_SUM; i++) {
    dp[i] = -1;
  }

  for(int i = 1; i <= n; i++) {
    ok[i] = true;
  }
  for(int r = 0; r < n; r++) {
    add(r);
    for(int l = 0; l <= r; l++) {
      ok[r - l + 1] &= possible(l, r);
    }
  }

  int cnt = 0;
  for(int sz = 1; sz <= n; sz++) {
    cnt += ok[sz];
  }
  printf("%d ", cnt);
  for(int sz = 1; sz <= n; sz++) {
    if(ok[sz]) {
      printf("%d ", sz);
    }
  }
  printf("\n");
}

int main() {
  int t;
  scanf("%d", &t);
  for(int i = 0; i < t; i++) {
#ifdef LOCAL
    printf("=== Test %d ===\n", i + 1);
#endif
    solve_test();
  }

  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve_test()':
Main.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d", &a[i]);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d", &t);
      |   ~~~~~^~~~~~~~~~

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