# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1073788 | 2024-08-24T21:02:15 Z | horiaboeriu | Kpart (eJOI21_kpart) | C++17 | 705 ms | 512 KB |
#include <stdio.h> #include <stdlib.h> #define MAX 50000 #define MAXN 1000 char f[MAXN + 1]; int v[MAXN + 1]; short dp[MAX + 1];//dp[x] este cea mai mare pozitie de pe care incepe un subsir cu suma x int main() { int t1, i1, n, i, sum, x, s, j, nr; scanf("%d", &t1); for (i1 = 0; i1 < t1; i1++) { scanf("%d", &n); sum = 0; for (i = 1; i <= n; i++) { f[i] = 0; scanf("%d", &v[i]); sum += v[i]; } sum = sum / 2 + 1; for (i = 0; i <= sum; i++) { dp[i] = 0; } //o sa fac dp si o sa iau fiecare secventa din n si ar trebui sa existe un subsir in acea secventa care sa aiba suma cat jumatatea din suma secventei for (i = 1; i <= n; i++) { for (x = sum - v[i]; x > 0; x--) { if (dp[x] > dp[x + v[i]]) { dp[x + v[i]] = dp[x]; } } dp[v[i]] = i;//suma v[i] se poate obtine de pe poz i s = 0; for (j = i; j > 0; j--) { s += v[j]; if (s % 2 > 0 || dp[s / 2] < j) { f[i - j + 1] = 1; } } } nr = 0; for (i = 1; i <= n; i++) { nr += 1 - f[i]; } printf("%d ", nr); for (i = 1; i <= n; i++) { if (f[i] == 0) { printf("%d ", i); } } printf("\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 440 KB | Output is correct |
2 | Correct | 18 ms | 440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 348 KB | Output is correct |
2 | Correct | 131 ms | 344 KB | Output is correct |
3 | Correct | 151 ms | 464 KB | Output is correct |
4 | Correct | 244 ms | 344 KB | Output is correct |
5 | Correct | 570 ms | 512 KB | Output is correct |
6 | Correct | 705 ms | 508 KB | Output is correct |
7 | Correct | 640 ms | 348 KB | Output is correct |