oj.uz

Submission #925554

# Submission time Handle Problem Language Result Execution time Memory
925554 2024-02-12T04:12:40 Z WanWan Bootfall (IZhO17_bootfall) C++14
0 / 100
 1 ms 2392 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 

const int MOD1 = (int)1e9 + 7;
int n;
int A[505];
unsigned long long ways[505*505]; // natural overflow

int cnt[505*500];
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n;
	int sum=0;
	for(int i=1;i<=n;i++){
		cin>>A[i];
		sum+=A[i];
	}
	ways[0]=1;
	ways[0]=1;
	ways[0]=1;

	for(int i=1;i<=n;i++){
		for(int j=sum;j>=0;j--){
			if(j-A[i]>=0)ways[j]=(ways[j]+ways[j-A[i]]);
			
		}
	}
	unordered_set<int>os;
	if(sum % 2 == 1){
		return cout << 0,0;
	}
	if(ways[sum/2] == 0){
		return cout << 0,0;
	}

	for(int i=1;i<=n;i++){ // remove this
		unordered_set<int>os;
		for(int j=0;j<=sum;j++){

			if(j-A[i]>=0)ways[j]=(ways[j]-ways[j-A[i]]);
		}
		for(int j=0;j<=(sum-A[i]+1)/2;j++){
			if(ways[j]){
				int diff=abs(j-((sum-A[i])-j));
				if(diff>=0)cnt[diff]++;
			}
		}
			
		for(int j=sum;j>=0;j--){ 
			if(j-A[i]>=0)ways[j]=(ways[j]+ways[j-A[i]]);
			
		}
	}
	vector<int>out;
	for(int j=1;j<=sum;j++){

		if(cnt[j] >= n){
			out.push_back(j);
		}
	}
	cout<<out.size()<<"\n";
	for(auto x:out)cout<<x<<" ";

}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -