Submission #1128121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128121		alikhan	Bootfall (IZhO17_bootfall)	C++20	13 / 100	1094 ms	480 KiB

bootfall

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define int long long
using namespace std;
const int N = 1e6+100;
int a[N];
int cnt1=0;
int n;
int p[N];
bool can(int x){
	p[0]=1;  
    bool mx=0;
    for(int i=0;i<=n;i++){ 
    	if(mx) break;
        for(int j=x-a[i];j>=0;j--){ 
            if(p[j]==1){ 
    			int bt=j+a[i];
                if(p[j+a[i]]==0) p[j+a[i]]=1; 
                if(p[bt]==p[x-bt] && p[x-bt]==1 && x-bt==bt) {
                	mx=1;
                	break;
				}
            } 
        } 
    }  
//    for(int i=1;i<=x;i++){ 
//        if(p[i]==1 && p[x-i]==1 && x-i==i) {
////        	cout<<x<<' '<<i<<' '<<x-i<<'\n';
//        	mx=1;
//        	break;
//		}
//    } 
    for(int i=1;i<=x;i++){
    	p[i]=0;
	}
    return mx;
}
bool rec(int x){
	a[n]=x;
	bool ok=1;
	for(int i=0;i<=n;i++){
		cnt1+=x;
		cnt1-=a[i];
		int old=a[i];
		a[i]=0;
		if(!can(cnt1)) ok=0;	
		a[i]=old;
		cnt1-=x;
		cnt1+=a[i];
	}
	return ok;
}
void al() {
    cin>>n;
    int x=0;
    for(int i=0;i<n;i++){  
        cin>>a[i]; 
        cnt1+=a[i]; 
    } 
    vector<int>v;
    for(int i=1;i<=cnt1;i++){
    	if(rec(i)) v.push_back(i);
	}
	cout<<v.size()<<'\n';
    for(auto i:v){
    	cout<<i<<' ';
	}
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        al();
    }
}

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