제출 #38278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38278		antimirage	Bootfall (IZhO17_bootfall)	C++14	100 / 100	573 ms	4116 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;

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++)
    {
        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);
}

컴파일 시 표준 에러 (stderr) 메시지

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