제출 #1338121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1338121		DangKhoizzzz	Bootfall (IZhO17_bootfall)	C++20	65 / 100	1094 ms	1232 KiB

bootfall

#include <bits/stdc++.h>
#define arr3 array <int , 3>
#define pii pair <int , int>
#define fi first
#define se second
#define BIT(x , k) ((x >> k)&1)
#define MASK(x) (1 << x)

using namespace std;

const int maxn = 500*500 + 10;
const int INF = 1e18;

int n, a[maxn];
bitset <maxn> ans;
bitset <maxn> dp;
bitset <maxn> tmp;

void solve()
{
    cin >> n;
    dp.reset(); dp[0] = 1;
    int sum = 0;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        sum += a[i];
        dp |= (dp << a[i]);
    }
    if(sum % 2 == 1 || dp[sum/2] == 0) {cout << 0 << '\n'; return;}
    ans.reset(); ans.flip();

    for(int i = 1; i <= n; i++)
    {
        dp.reset();
        tmp.reset();
        dp[0] = 1;
        for(int j = 1; j <= n; j++)
        {
            if(i != j) dp |= (dp << a[j]);
        }
        for(int j = 0; 2*j <= sum - a[i]; j++)
        {
            if(dp[j]) tmp[sum - a[i] - 2*j] = 1;
        }
        ans &= tmp;
    }
    vector <int> print;
    for(int i = 0; i < 500*500; i++) 
    {
        if(ans[i]) print.push_back(i);
    }
    cout << print.size() << '\n';
    for(int x: print) cout << x << ' ';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    solve();
    return 0;
}

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

bootfall.cpp:12:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   12 | const int INF = 1e18;
      |                 ^~~~

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