Submission #1367440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367440		jbn8	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1095 ms	1872 KiB

bootfall

#include <cstdio>
#include <array>
#include <cassert>
using namespace std;

const int maxN = 500;
const int maxA = 501;
int main(){
    int N;
    scanf("%d\n", &N);
    array<int, maxN+1> a{};
    array<bool, maxA> already{};
    int sum = 0;
    for(int i=0; i<N; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    array<int, maxA*maxN> poss{};
    array<bool, maxN*maxA/2> cache{};
    cache[0] = true;
    int duplicate = 0;
    for(int i=0; i<N+1; i++){
        int part = sum-a[i];
        if(i){
            int idp = i-1;
            for(int j=sum/2; j >= 0; j--){
                if(cache[j]){
                    cache[j+a[idp]] = true;
                }
            }
        }
        if(already[a[i]]){
            duplicate++;
            continue;
        }
        already[a[i]] = true;
        array<bool, maxN*maxA/2> possreferee = cache;
        for(int idp=i+1; idp<N; idp++){
            for(int j=part/2-a[idp]; j >= 0; j--){
                if(possreferee[j]){
                    possreferee[j+a[idp]] = true;
                }
            }
        }
        if(i == N && !possreferee[part/2]){
            printf("0\n");
            return 0;
        }
        if(i == N)continue;
        for(int idw=0; idw<=part/2; idw++){
            if(possreferee[idw]){
                poss[part-idw*2]++;
            }
        }
    }
    int count = 0;
    for(int i=0; i<sum; i++)
        count += poss[i] == N-duplicate;
    printf("%d\n", count);
    if(count){
        for(int i=0; i<sum; i++){
            if(poss[i] == N-duplicate){
                printf("%d ", i);
            }
        }
        printf("\n");
    }
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d\n", &N);
      |     ~~~~~^~~~~~~~~~~~
bootfall.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 0 / 35