Submission #672422

#	Time	Username	Problem	Language	Result	Execution time	Memory
672422		Cutebol	Bootfall (IZhO17_bootfall)	C++17	100 / 100	249 ms	5704 KiB

bootfall

#include <bits/stdc++.h>
 
using namespace std;
 
void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
   
const int N = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e12 ;

int n , sum ;
int a[250005] , dp[250005] , vis[250005] ;

void solve(){
	
	cin >> n ;
	for ( int i = 0 ; i < n ; i ++ ){
		cin >> a[i] ;
		sum += a[i] ;
	}
	dp[0] ++ ;
	for ( int i = 0 ; i < n ; i ++ )
		for( int j = sum ; j - a[i] >= 0 ; j -- ) dp[j] += dp[j-a[i]] ;
	
	if ( !dp[sum/2] || sum % 2 ){
		cout << 0 ;
		return ;
	}
	for ( int i = 0 ; i < n ; i ++ ){
		int cur = sum - a[i] ;
		for ( int j = a[i] ; j <= sum ; j ++ )
			dp[j] -= dp[j-a[i]] ;
		for ( int j = 0 ; j <= cur/2 ; j ++ )
			if ( dp[j] ) vis[cur-j*2] ++ ;
		for ( int j = sum ; j >= a[i] ;j -- ) dp[j] += dp[j-a[i]] ;
	}vector <int> ans ;
	for ( int i = 0 ; i < sum + 1 ; i ++ ) if ( vis[i] == n ) ans.push_back(i) ;
	cout <<
	 ans.size() << '\n' ;
	for ( auto ti : ans ) cout << ti << ' ' ;
	
}
 
signed main(){
//  fopn("blocks") ;
    Scaramouche ;
    int t = 1 ;
//      cin >> t ;
    while ( t -- ) solve() ; 
}

Compilation message (stderr)

bootfall.cpp: In function 'void fopn(std::string)':
bootfall.cpp:5:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:5:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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