Submission #1128086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128086		azik	Bootfall (IZhO17_bootfall)	C++20	13 / 100	1094 ms	492 KiB

bootfall

#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin() , v.end()
using namespace std;
int n , m ;
const int N = 521;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n ;
    int sum =0 ;
    vector<int>a;
    for(int i= 1 ; i <= n; i++){
        int h;cin>>h;
        sum+=h;
        a.pb(h);
    }
    if(n<= 1 ){
        cout << 0 ;
        return 0 ;
    }
    sum*=5;
    vector<int>ans;
    for(int x = 0 ; x <= sum  ; x++) {
        a.pb(x);
        int ok =0 ;
        for(int pos = 0 ; pos < n ;pos++) {
            if( x == 0 )pos = n ;
            int sum2 = 0;
            vector<int> dp(sum, 0);
            dp[0] = 1;
            for (int i = 0; i < a.size(); i++) {
                if (i == pos)continue;
                sum2 += a[i];
            }
            //cout << a[pos] << ' ' << x << ' ' << sum2 << '\n';
            if (sum2 % 2 != 0) {
                ok = 1;
                break;
            }
            sum2 /= 2;
            for (int i = 0; i < a.size(); i++) {
                if (i == pos)continue;
                for (int j = sum2; j >= a[i]; j--) {
                    if (dp[j - a[i]] == 1)dp[j] = 1;
                }
            }
            if (!dp[sum2]) {
                ok = 1;
                break;
            }
        }
        if(x == 0 && ok){
            cout << 0 ;
            return 0 ;
        }
        if(!ok && x > 0 ){
            ans.pb(x);
        }
        a.pop_back();
    }
    cout<< ans.size() << '\n';
    for(auto it:ans){
        cout << it << ' ';
    }
}

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