Submission #94409

#	Time	Username	Problem	Language	Result	Execution time	Memory
94409		Kastanda	Bootfall (IZhO17_bootfall)	C++11	100 / 100	406 ms	1960 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
const int N = 505, SQ = 24;
int n, sum, A[N];
bitset < N * N > T, R, B, P[SQ];
int main()
{
    scanf("%d", &n);
    bool odd = 0, even = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
        sum += A[i];
        if (A[i] & 1) odd = 1;
        else even = 1;
    }
    if (odd && even)
        return !printf("0");
    if (odd && (n & 1))
        return !printf("0");

    for (int i = 0; i <= (n - 1) / SQ; i++)
    {
        P[i][0] = 1;
        int l = i * SQ, r = min(l + SQ, n);
        for (int j = 0; j < n; j++)
            if (j < l || r <= j)
                P[i] |= P[i] << A[j];
    }
    B[0] = 1;
    for (int j = 0; j < n; j++)
        B |= B << A[j];
    if (!B[sum >> 1])
        return !printf("0");

    for (int j = 1; j < N * N; j++)
        R[j] = 1;

    for (int i = 0; i < n; i++)
    {
        int block = i / SQ;
        int l = block * SQ, r = min(l + SQ, n);
        B = P[block];
        for (int j = l; j < r; j++)
            if (j != i)
                B |= B << A[j];
        int _sum = sum - A[i];
        int half = (_sum + 2) >> 1;
        T = 0;
        for (int j = half; j <= _sum; j++)
            if (B[j]) T[j + j - _sum] = 1;
        R = R & T;
    }
    printf("%d\n", (int)R.count());
    for (int j = 1; j < N * N; j++)
        if (R[j]) printf("%d ", j);
    return 0;
}

Compilation message (stderr)

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