oj.uz

Submission #793236

# Submission time Handle Problem Language Result Execution time Memory
793236 2023-07-25T16:27:52 Z rainboy Kpart (eJOI21_kpart) C
100 / 100
 717 ms 588 KB 
#include <stdio.h>
#include <string.h>

#define N	1000
#define S	50000

int max(int a, int b) { return a > b ? a : b; }

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int aa[N], dp[S + 1];
		static char good[N + 1];
		int n, k, i, j, s, cnt;

		scanf("%d", &n);
		memset(dp, -1, (S + 1) * sizeof *dp);
		memset(good, 1, (n + 1) * sizeof *good);
		for (j = 0; j < n; j++) {
			scanf("%d", &aa[j]);
			for (s = S; s >= aa[j]; s--)
				dp[s] = max(dp[s], dp[s - aa[j]]);
			dp[aa[j]] = j;
			s = 0;
			for (i = j; i >= 0; i--) {
				s += aa[i];
				if (s % 2 != 0 || dp[s / 2] < i)
					good[j - i + 1] = 0;
			}
		}
		cnt = 0;
		for (k = 1; k <= n; k++)
			if (good[k])
				cnt++;
		printf("%d", cnt);
		for (k = 1; k <= n; k++)
			if (good[k])
				printf(" %d", k);
		printf("\n");
	}
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:12:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
Main.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
Main.c:22:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |    scanf("%d", &aa[j]);
      |    ^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 468 KB Output is correct
2 Correct 79 ms 484 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 468 KB Output is correct
2 Correct 272 ms 512 KB Output is correct
3 Correct 274 ms 496 KB Output is correct
4 Correct 383 ms 508 KB Output is correct
5 Correct 573 ms 524 KB Output is correct
6 Correct 717 ms 512 KB Output is correct
7 Correct 644 ms 588 KB Output is correct