Submission #1367442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1367442		jbn8	Bootfall (IZhO17_bootfall)	C++20	0 / 100	118 ms	246848 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;
    array<array<int, maxN*maxA/2>, maxN> backward{};
    array<int, maxN> sizeBck{};
    array<bool, maxN*maxA/2> possbck{};
    possbck[0] = true;
    for(int i=N-1; i >= 0; i--){
        for(int j=sum/2-a[i]; j >= 0; j--){
            if(possbck[j]){
                possbck[j+a[i]] = true;
            }
        }
        for(int idx=0; idx<=sum/2; idx++){
            backward[i][sizeBck[i]] = idx;
            sizeBck[i] += possbck[idx];
        }
    }
    for(int i=0; i<N+1; i++){
        int part = sum-a[i];
        if(i){
            int idp = i-1;
            for(int j=sum/2-a[i]; 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 j=part/2; j >= 0; j--){
            if(possreferee[j]){
                for(int k=0; k<sizeBck[i+1]; k++){
                    possreferee[j+backward[i+1][k]] = 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: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35