제출 #697022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697022		allllekssssa	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	507 ms	17940 KiB

subsequence

#include<bits/stdc++.h>
 
using namespace std;
 
const int maxN = 500 + 3;
const int bsSize = maxN * maxN + 10;
int n;
int a[maxN];
int cnt[maxN];
bitset<bsSize> dp[2][maxN], pre;
 
int main() {
 
	//cin >> n;
   n = 500;	
  int sum = 0;
    int gc = 0;
	for (int i = 1; i<=n; i++) {
	    //cin >> a[i];
        a[i] = min(2 * i - 1, 499);
		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;
		}
		cnt[a[i]]++;
		sum+=a[i];
	}
 
	if (sum & 1) {
    	printf("0\n");
    	return 0;    	
    }
    
 
	for (int i = 1; i <= 501; i++) {
		dp[0][i].set(0);
	}
    
    int par = 0;
	for (int i = 1; i < 500; i+=2) {
		bool updated = false;
		par^=1;
		for (int j = 1; j <= 501; j+=2) {
			if (j < 501 && !cnt[j]) continue;
			
			if (i == j) {
				dp[par][j] = dp[par ^ 1][j] | (dp[par ^ 1][j] << (j * (cnt[j]-1)));
			} else {
					if (updated) {
						dp[par][j] = pre;
					} else {
					dp[par][j] = dp[par ^ 1][j] | (dp[par ^ 1][j] << (j * cnt[j]));
					if (i < j && !updated) {
			   			pre = dp[par][j];
			   			updated = true;
			   	    }
			   	}
			 }
		}
	}
 
 
	if (dp[par][501][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 < 500; j+=2) {
        	if (!cnt[j]) continue;
        	int totSum = sum  - j + i;
        	if (totSum % 2 == 1) ok = false;
        	if (dp[par][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 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60