Submission #537600

#	Time	Username	Problem	Language	Result	Execution time	Memory
537600		dantoh000	Kpart (eJOI21_kpart)	C++14	100 / 100	1757 ms	852 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70