Submission #337922

#	Time	Username	Problem	Language	Result	Execution time	Memory
337922		kutbilim_one	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1092 ms	34132 KiB

bootfall

/** kutbilim.one **/
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(),x.end()
#define int long long
#define endl '\n'
                 /*   
ifstream in("test.txt"); 
#define cin in    */

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

	int n; cin >> n;
	vector<int> a(n);
	int sum = 0;
	for(int i = 0; i < n; i++) 
		cin >> a[i], sum += a[i];

	sort(all(a));
	map<int, set<int>> cnt;
                 
	int MAX = sum;
	vector<int> dp(MAX+1); 
	dp[0] = 1;
	for(int k = 0; k < n; k++){
  	 	for(int x = MAX-a[k]; x >= 0; x--){
   			dp[x+a[k]] |= dp[x];
    	} 
    }

    int good = false;
    for(int left = 0, right; left <= MAX; left++){
		if(!dp[left]) continue;
		right = MAX-left;
		if(left == right) good = true;
	}

	if(!good) goto breaker;		
	for(int ex = 0; ex < n; ex++){
		MAX = sum-a[ex];
		vector<int> pd(MAX+1); 
		pd[0] = 1;
		for(int k = 0; k < n; k++){
  			if(k == ex) continue;
  		 	for(int x = MAX-a[k]; x >= 0; x--){
   				pd[x+a[k]] |= pd[x];
    		} 
    	}	     
		
		for(int left = 1, right; left <= MAX; left++){
			if(!pd[left]) continue;
			right = MAX-left;
			cnt[abs(left-right)].insert(ex);
		}
	}
	breaker:;

	stringstream resultOut;
	int sizeOut = 0;
	for(auto i : cnt){
		if(i.second.size() == n) 
			resultOut << i.first << " ", sizeOut++;
	}

	cout << sizeOut << endl << resultOut.str();
    
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:65:22: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   65 |   if(i.second.size() == n)
      |      ~~~~~~~~~~~~~~~~^~~~

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