oj.uz

Submission #1073784

# Submission time Handle Problem Language Result Execution time Memory
1073784 2024-08-24T20:58:26 Z horiaboeriu Kpart (eJOI21_kpart) C++17
100 / 100
 607 ms 852 KB 
#include <stdio.h>
#include <stdlib.h>
#define MAX 50000
#define MAXN 1000
char f[MAXN + 1];
int v[MAXN + 1], dp[2][MAX + 1];//dp[i][x] este cea mai mare pozitie de pe care incepe un subsir cu suma x care se termina pe o pozitie <= i
//dar voi tine mereu doar pentru i si i - 1 ca sa nu ocup foarte multa memorie
int main()
{
    int t1, i1, n, i, t, sum, x, s, j, nr;
    scanf("%d", &t1);
    for (i1 = 0; i1 < t1; i1++) {
        for (i = 0; i <= MAX; i++) {
            dp[0][i] = dp[1][i] = 0;
        }
        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;
        //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
        t = 1;
        for (i = 1; i <= n; i++) {
            for (x = sum - v[i]; x > 0; x--) {
                dp[t][x + v[i]] = dp[1 - t][x] > dp[1 - t][x + v[i]] ? dp[1 - t][x] : dp[1 - t][x + v[i]];
            }
            for (x = 0; x < v[i]; x++) {
                dp[t][x] = dp[1 - t][x];//x nu se poate obtine cu v[i], deci rezultatul este cel de la i - 1
            }
            dp[t][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[t][s / 2] < j) {
                    f[i - j + 1] = 1;
                }
            }
            t = 1 - t;
        }

        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

Main.cpp: In function 'int main()':
Main.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &t1);
      |     ~~~~~^~~~~~~~~~~
Main.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
Main.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |             scanf("%d", &v[i]);
      |             ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 9 ms 604 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 600 KB Output is correct
2 Correct 92 ms 828 KB Output is correct
3 Correct 104 ms 604 KB Output is correct
4 Correct 194 ms 840 KB Output is correct
5 Correct 458 ms 820 KB Output is correct
6 Correct 607 ms 848 KB Output is correct
7 Correct 551 ms 852 KB Output is correct