Submission #133852

#	Time	Username	Problem	Language	Result	Execution time	Memory
133852		Kastanda	Bootfall (IZhO17_bootfall)	C++11	44 / 100	334 ms	2112 KiB

bootfall

// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 505, MXN = N * N, Mod = 1e9 + 9;
int n, SM, A[N], B[MXN], dp[MXN];
inline void Add(int a)
{
    for (int i = MXN - 1; i >= a; i --)
    {
        dp[i] += dp[i - a];
        if (dp[i] >= Mod)
            dp[i] -= Mod;
    }
}
inline void Del(int a)
{
    for (int i = a; i < MXN; i ++)
    {
        dp[i] -= dp[i - a];
        if (dp[i] < 0)
            dp[i] += Mod;
    }
}
int main()
{
    scanf("%d", &n); dp[0] = 1;
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]), Add(A[i]), SM += A[i];
    if (SM % 2 || !dp[SM / 2])
        return !printf("0\n");
    for (int i = 1; i <= n; i ++)
    {
        Del(A[i]);
        SM -= A[i];
        for (int k = (SM + 1 & 1) + 1; k <= SM; k += 2)
            if (dp[(k + SM >> 1) - k])
                B[k] ++;
        SM += A[i];
        Add(A[i]);
    }
    int r = 0;
    for (int k = 1; k <= SM; k ++)
        if (B[k] == n) r ++;
    printf("%d\n", r);
    for (int k = 1; k <= SM; k ++)
        if (B[k] == n)
            printf("%d ", k);
    printf("\n");
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:35:26: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
         for (int k = (SM + 1 & 1) + 1; k <= SM; k += 2)
                       ~~~^~~
bootfall.cpp:36:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             if (dp[(k + SM >> 1) - k])
                     ~~^~~~
bootfall.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n); dp[0] = 1;
     ~~~~~^~~~~~~~~~
bootfall.cpp:28:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]), Add(A[i]), SM += A[i];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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