Submission #95520

#	Time	Username	Problem	Language	Result	Execution time	Memory
95520		choikiwon	Bootfall (IZhO17_bootfall)	C++17	100 / 100	555 ms	2092 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;

const int MN = 502;
const int SQ = 10;

int N;
int A[MN];
bitset<MN * MN> dp, tmp;
int cnt[MN * MN];

int main() {
    scanf("%d", &N);

    int sum = 0;
    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        sum += A[i];
    }
    if(sum % 2) {
        printf("0");
        return 0;
    }

    dp[0] = 1;
    for(int i = 0; i < N; i++) {
        dp |= (dp << A[i]);
    }
    if(!dp[sum / 2]) {
        printf("0");
        return 0;
    }

    for(int l = 0; l < N; l += SQ) {
        int r = min(N, l + SQ) - 1;

        dp.reset();
        dp[0] = 1;
        for(int i = 0; i < N; i++) {
            if(l <= i && i <= r) continue;
            dp |= (dp << A[i]);
        }

        for(int i = l; i <= r; i++) {
            tmp = dp;

            for(int j = l; j <= r; j++) {
                if(j == i) continue;
                tmp |= (tmp << A[j]);
            }

            for(int j = 0; j < MN * MN; j++) {
                if(tmp[j] && 2 * j + A[i] - sum >= 0) {
                    cnt[ 2 * j + A[i] - sum ]++;
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < MN * MN; i++) {
        if(cnt[i] == N) ans++;
    }
    printf("%d\n", ans);
    for(int i = 0; i < MN * MN; i++) {
        if(cnt[i] == N) printf("%d ", i);
    }
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
bootfall.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         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: 35 / 35