oj.uz

Submission #537494

# Submission time Handle Problem Language Result Execution time Memory
537494 2022-03-15T07:24:01 Z tqbfjotld Kpart (eJOI21_kpart) C++14
30 / 100
 2000 ms 844 KB 
#include <bits/stdc++.h>
using namespace std;

int pre[1005];
int arr[1005];
bool can[1005][1005];

int main(){
    int TC;
    scanf("%d",&TC);
    while (TC--){
        int n;
        scanf("%d",&n);
        for (int x = 0; x<n; x++){
            scanf("%d",&arr[x]);
            if (x==0) pre[x] = arr[x];
            else pre[x] = arr[x]+pre[x-1];
        }
        for (int x = 0; x<n; x++){
            bitset<100005> bs;
            bs[0] = true;
            for (int y = x; y<n; y++){
                bs = bs | (bs<<arr[y]);
                int sm = pre[y]-(x==0?0:pre[x-1]);
                //printf("tt %d\n",sm);
                if (sm&1) can[x][y] = false;
                else can[x][y] = bs[sm/2];
                //printf("can %d %d = %d\n",x,y,can[x][y]);
            }
        }
        vector<int> ans;
        for (int x = 1; x<=n; x++){
            bool t = true;
            for (int y = 0; y+x<=n; y++){
                if (!can[y][y+x-1]){
                    t = false;
                    break;
                }
            }
            if (t) ans.push_back(x);
        }
        printf("%d ",ans.size());
        for (auto x : ans) printf("%d ",x);
        printf("\n");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:42:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   42 |         printf("%d ",ans.size());
      |                 ~^   ~~~~~~~~~~
      |                  |           |
      |                  int         std::vector<int>::size_type {aka long unsigned int}
      |                 %ld
Main.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     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",&arr[x]);
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 412 KB Output is correct
2 Correct 385 ms 444 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1739 ms 584 KB Output is correct
2 Execution timed out 2078 ms 844 KB Time limit exceeded
3 Halted 0 ms 0 KB -