oj.uz

Submission #537600

# Submission time Handle Problem Language Result Execution time Memory
537600 2022-03-15T09:32:22 Z dantoh000 Kpart (eJOI21_kpart) C++14
100 / 100
 1757 ms 852 KB 
#include <bits/stdc++.h>
using namespace std;
map<int,int> ct;
int tc;
int n;
int can[1005];
int a[1005];
int lst[100005];
int p[1005];
int main(){
    scanf("%d",&tc);
    while (tc--){
        scanf("%d",&n);
        for (int i = 1; i <= n; i++){
            scanf("%d",&a[i]);
            p[i] = a[i] + p[i-1];
        }
        lst[0] = 0;
        for (int i = 1; i <= n; i++) can[i] = 1;
        for (int i = 1; i <= 100000; i++) lst[i] = -1;
        for (int i = 1; i <= n; i++){
            for (int j = 100000-a[i]; j >= 0; j--){
                if (lst[j] == -1) continue;
                lst[j+a[i]] = max(lst[j], lst[j+a[i]]);
            }
            for (int k = 1; k <= i; k++){
                int s = p[i]-p[i-k];
                if (s % 2 == 1 || lst[s/2] < i-k+1){

                    can[k] = false;
                }
            }
            lst[0] = i;
        }
        int ct = 0;
        for (int i = 0; i <= n; i++) {
            ct += can[i];
        }
        printf("%d ",ct);
        for (int i = 0; i <= n; i++) {
            if (can[i]) printf("%d ",i);
        }
        printf("\n");
    }

}

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",&tc);
      |     ~~~~~^~~~~~~~~~
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:15:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |             scanf("%d",&a[i]);
      |             ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 696 KB Output is correct
2 Correct 163 ms 684 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 688 KB Output is correct
2 Correct 579 ms 808 KB Output is correct
3 Correct 595 ms 728 KB Output is correct
4 Correct 844 ms 852 KB Output is correct
5 Correct 1332 ms 720 KB Output is correct
6 Correct 1757 ms 836 KB Output is correct
7 Correct 1740 ms 824 KB Output is correct