Submission #868534

#	Time	Username	Problem	Language	Result	Execution time	Memory
868534		Charizard2021	Bootfall (IZhO17_bootfall)	C++17	100 / 100	435 ms	7932 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
const int N = 250000;
const int M = 1000000;
const int MOD = 1e9 + 7;
int n;
int v[502];
int freq[1 + M];
bool dp[1 + N];
int dp2[1 + N];
int dp3[1 + N];
int firstVal[1 + N];
int lastVal[1 + N];
bool solve(int x){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if(i != x){
            sum += v[i];
        }
    }
    if(x == 0){
        int maxVal = 0;
        dp[0] = 1;
        dp2[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = maxVal; j >= 0; j--){
                if(dp[j]){
                    dp2[j + v[i]] = (dp2[j + v[i]] + dp2[j]) % MOD;
                    if(!firstVal[j + v[i]]){
                        firstVal[j + v[i]] = i;
                    }
                    lastVal[j + v[i]] = i;
                    dp[j + v[i]] = 1;
                }
            }
            maxVal += v[i];
        }
        if(maxVal % 2 == 0 && dp[maxVal/2]){
            return 1;
        }
        return 0;
    }
    else{
        for(int j = 0; j <= sum + v[x]; j++){
            dp3[j] = dp2[j];
        }
        for(int j = v[x]; j <= sum + v[x]; j++){
            dp2[j] = (((dp2[j] - dp2[j - v[x]]) % MOD) + MOD) % MOD;
        }
        for(int i = 0; i <= sum/2; i++){
            if(dp2[i]){
                freq[sum - 2 * i]++;
            }
        }
        for(int j = 0; j <= sum + v[x]; j++){
            dp2[j] = dp3[j];
        }
        return true;
    }
}
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    bool thing = solve(0);
    if(thing == false){
        cout << 0 << "\n";
        return 0;
    }
    for(int i = 1; i <= n; i++) solve(i);
    int ans = 0;
    vector<int> val;
    for(int i = 0; i <= M; i++){
        if(freq[i] == n){
            ans++;
            val.push_back(i);
        }
    }
    cout << ans << "\n";
    for(int x : val){
        cout << x << " ";
    }
    cout << "\n";
}

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