| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 91457 | davitmarg | Bootfall (IZhO17_bootfall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n,a[502],cant[502 * 502*4];
int sum,sm;
vector<int> ans;
LL dp[502 * 502*4];
void add(LL k) {
for (int i = sum; i >= k; i--) {
dp[i] += dp[i - k];
}
}
void rem(LL k) {
for (int i = k; i <= sum; i++) {
dp[i] -= dp[i - k];
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
sum += a[i];
}
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = sum; j >= 0; j--)
dp[j + a[i]]+=dp[j];
if (sum % 2==1 || dp[sum / 2] == 0)
{
cout << 0 << endl;
return 0;
}
sm = sum;
for (int i = 0; i < n; i++)
{
rem(a[i]);
sum -= a[i];
for (int j = 0; j <= sm*2; j++)
if ((sum+j) % 2==1 || dp[(sum+j) / 2] == 0)
cant[j] = 1;
add(a[i]);
sum += a[i];
}
for (int j = 0; j <= sm; j++)
if (!cant[j])
ans.PB(j);
cout << ans.size() << endl;
if (ans.size() == 0)
return;
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
cout << endl;
return 0;
}