oj.uz

답안 #697018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
697018 2023-02-07T23:05:16 Z allllekssssa Bootfall (IZhO17_bootfall) C++14
0 / 100
 0 ms 340 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
const int maxN = 500 + 2;
const int bsSize = maxN * maxN + 10;
const int limit = 18900;
int n;
int a[maxN];
int cnt[maxN];
bitset<bsSize> dp[2][maxN], pre;
bitset<limit> dp1[2][maxN], pre1;
 
int main() {
 
    cin >> n;
  
	int sum = 0;
    int gc = 0;
	for (int i = 1; i<=n; i++) {
	    cin >> a[i];
		gc = __gcd(a[i], gc);
	}
 
	for (int i = 1; i<=n; i++) {
		a[i]/=gc;
		if ((a[i] & 1) == 0) {
			printf("0\n");
			return 0;
		}
		if (cnt[a[i]] == 0) cnt[a[i]] = i;
		sum+=a[i];
	}
    
    cout << sum << endl;
 
	for (int i = 1; i <= n + 1; i++) {
		dp[0][i].set(0);
		dp1[0][i].set(0);
	}
 
	for (int i = 1; i<=n; i++) {
		bool updated = false;
		for (int j = 1; j <= n + 1; j++) {
			if (j<= n && cnt[a[j]] != j) continue;
			if (sum < limit) {
			if (i == j) {
				dp1[i&1][j] = dp1[(i&1) ^ 1][j];
			} else {
					if (updated) {
						dp1[i&1][j] = pre1;
					} else {
					dp1[i&1][j] = dp1[(i&1) ^ 1][j] | (dp1[(i&1) ^ 1][j] << a[i]);
					if (i < j && !updated) {
			   			pre1 = dp1[i&1][j];
			   			updated = true;
			   	    }
			   	}
			 }
 
			} else {
			
			if (i == j) {
				dp[i&1][j] = dp[(i&1) ^ 1][j];
			} else {
					if (updated) {
						dp[i&1][j] = pre;
					} else {
					dp[i&1][j] = dp[(i&1) ^ 1][j] | (dp[(i&1) ^ 1][j] << a[i]);
					if (i < j && !updated) {
			   			pre = dp[i&1][j];
			   			updated = true;
			   	    }
			   	}
			 }
		  }
		}
	}
    
    if (sum & 1) {
    	printf("0\n");
    	return 0;    	
    }
 
	if ((sum >= limit && dp[n&1][n + 1][sum/2] == 0) || (sum < limit && dp1[n&1][n + 1][sum/2] == 0)) {
		printf("0\n");
		return 0;
	}
 
    vector<int> ans;
 
	for (int i = 1; i <= sum; i+=2) {
		bool ok = true;
         
        for (int j = 1; j<= n; j++) {
        	if (cnt[a[j]] != j) continue;
        	int totSum = sum  - a[j] + i;
        	if (totSum % 2 == 1) ok = false;
        	if ((sum>= limit && dp[n&1][j][totSum/2] == 0) || (sum < limit && dp1[n&1][j][totSum/2] == 0)) ok = false;
        }
 
		if (ok) ans.push_back(i);
	}
 
	cout << ans.size() << endl;
 
	for (int i:ans) {
		printf("%d ", i * gc);
	}
 
	cout << endl;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -