oj.uz

Submission #640384

# Submission time Handle Problem Language Result Execution time Memory
640384 2022-09-14T13:44:15 Z Kanimet0 Kpart (eJOI21_kpart) C++17
100 / 100
 1543 ms 812 KB 
#include <cstdio>
#include <math.h>

const int maxv = 1e5;

int n, cnt;
int A[maxv + 1], pref[maxv + 1], ans[maxv + 1];
short dp[maxv + 1];

void solve() {
    scanf("%d", &n);
    for(short i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        ans[i] = true;
        pref[i] = pref[i - 1] + A[i];
    }
    dp[0] = maxv + 1;
    for(int j = 1; j <= maxv; j++) dp[j] = 0;
    int s = -1;
    for(short i = 1; i <= n; i++) {
        for(int j = maxv; j > A[i]; --j) dp[j] = std::max(dp[j], dp[j - A[i]]);
        dp[A[i]] = i;
        for(short k = 1; k <= i; k++) {
            s = (pref[i] - pref[k-1]);
            if((s & 1) || (dp[s / 2] < k)) ans[i - k + 1] = false;
        }
    }
    cnt = 0;
    for(short i = 1; i <= n; i++) if(ans[i]) cnt++;
    printf("%d", cnt);
    for(short i = 1; i <= n; i++) if(ans[i]) printf(" %d", i);
    printf("\n");
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:17:18: warning: overflow in conversion from 'int' to 'short int' changes value from '100001' to '-31071' [-Woverflow]
   17 |     dp[0] = maxv + 1;
      |             ~~~~~^~~
Main.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 500 KB Output is correct
2 Correct 182 ms 488 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 500 KB Output is correct
2 Correct 593 ms 520 KB Output is correct
3 Correct 593 ms 648 KB Output is correct
4 Correct 832 ms 528 KB Output is correct
5 Correct 1258 ms 676 KB Output is correct
6 Correct 1543 ms 584 KB Output is correct
7 Correct 1387 ms 812 KB Output is correct