# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
855101 | Alfraganus | Bootfall (IZhO17_bootfall) | C++17 | 351 ms | 262144 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fs first
#define ss second
#define endl '\n'
#define all(a) a.begin(), a.end()
#define print(a) \
for(auto x : a) \
cout << x << ' '; \
cout << endl;
#define printmp(a) \
for (auto x : a) \
cout << x.fs << ' ' << x.ss << endl;
void solve(){
int n;
cin >> n;
vector<int> a(n);
int sum = 0;
bool even = false, odd = false;
for(int i = 0; i < n; i ++)
cin >> a[i], sum += a[i], even |= !(a[i] & 1), odd |= (a[i] & 1);
sort(all(a));
if((sum & 1)){
cout << 0;
return;
}
if(even and odd){
cout << 0;
return;
}
queue<int> q;
q.push(sum / 2);
bool flag = false;
while(!q.empty()){
int x = q.front();
q.pop();
if(x == 0)
flag = 1;
if(!flag){
for(int i = 0; i < n; i ++){
if(x >= a[i]){
q.push(x - a[i]);
}
}
}
}
if(!flag){
cout << 0;
return;
}
vector<vector<bool>> dp(n, vector<bool> (sum));
for(int i = 0; i < n; i ++){
dp[i][0] = 1;
vector<int> b;
for(int j = 0; j < n; j ++){
if(i != j){
dp[i][a[j]] = 1;
for (auto x : b)
{
if (x + a[j] < dp[0].size() and dp[i][x + a[j]] == 0)
{
dp[i][x + a[j]] = 1;
b.push_back(x + a[j]);
}
}
b.push_back(a[j]);
}
}
b.clear();
}
if(even){
vector<int> ans;
for(int j = 2; j <= sum - a[0]; j += 2){
int c = sum;
for(int i = 0; i < n; i ++){
sum -= a[i];
sum += j;
if(!((sum / 2 < dp[0].size() and sum / 2 >= 0 and dp[i][sum / 2]) or (sum / 2 - j < dp[0].size() and sum / 2 >= j and dp[i][sum / 2 - j])))
break;
sum -= j;
sum += a[i];
if(i == n - 1)
ans.push_back(j);
}
sum = c;
}
cout << ans.size() << endl;
print(ans)
}
else{
vector<int> ans;
for (int j = 1; j <= sum - a[0]; j += 2)
{
int c = sum;
for (int i = 0; i < n; i++)
{
sum -= a[i];
sum += j;
if (!((sum / 2 < dp[0].size() and sum / 2 >= 0 and dp[i][sum / 2]) or (sum / 2 - j < dp[0].size() and sum / 2 >= j and dp[i][sum / 2 - j])))
break;
sum -= j;
sum += a[i];
if (i == n - 1)
ans.push_back(j);
}
sum = c;
}
cout << ans.size() << endl;
print(ans)
}
}
signed main(){
int t = 1;
// cin >> t;
while(t --){
solve();
cout << endl;
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |