Submission #1233156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233156		fermat	Bootfall (IZhO17_bootfall)	C++20	100 / 100	224 ms	2752 KiB

bootfall

#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )

using namespace std;

const int N = 505, mod = 1e9 + 7;

int dp[N * N], mx = 500 * 500, u[N];

int n, ar[N], sum;

vector <int> ans;

void add (int val)
{
    for (int i = sum; i >= 0; i--)
        dp[i + val] += dp[i];

    sum += val;
}
void del (int val)
{
    sum -= val;

    for (int i = 0; i <= sum; i++)
        dp[i + val] -= dp[i];
}

bool is[N * N];

main ()
{
    dp[0] = 1;

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &ar[i]);
        add(ar[i]);
    }
    if (sum % 2 == 1 || dp[ sum / 2 ] == 0)
    {
        puts("0");
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        if (u[ar[i]]) continue;

        u[ ar[i] ] = 1;

        del(ar[i]);

        for (int j = 1; j <= mx; j++)
        {
            if ( (sum + j) % 2 || !dp[ (sum + j) / 2 ] )
                is[j] = 1;
        }
        add(ar[i]);
    }
    for (int i = 1; i <= mx; i++)
        if (!is[i]) ans.pb(i);

    cout << ans.size() << endl;

    for (auto it : ans)
        printf("%d ", it);
}

Compilation message (stderr)

bootfall.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main ()
      | ^~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d", &ar[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