| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 173621 | aleks5d | Bootfall (IZhO17_bootfall) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using ll = long long int;
using ull = unsigned long long int;
using dd = double;
using ldd = long double;
namespace HASH {
const ll mod197 = 1e9 + 7;
const ll mod199 = 1e9 + 9;
const ll modfft = 998244353;
ll MOD = mod197;
void Hplus(ll& h, ll b, ll mod = MOD) {
h += b;
if (h > mod)
h -= mod;
}
void Hminus(ll& h, ll b, ll mod = MOD) {
h -= b;
if (h < 0)
h += mod;
}
void Hmuliply(ll& h, ll b, ll mod = MOD) {
h *= b;
h %= mod;
}
ll Hdivider(ll x, ll mod = MOD) {
if (x < 0)
x += mod;
ll ans = 1;
ll n = mod - 2;
while (n) {
if (n & 1)
Hmuliply(ans, x);
n >>= 1;
Hmuliply(x, x);
}
return ans;
}
}
namespace someUsefull {
template<typename T1, typename T2>
inline void checkMin(T1& a, T2 b) {
if (a > b)
a = b;
}
template<typename T1, typename T2>
inline void checkMax(T1& a, T2 b) {
if (a < b)
a = b;
}
}
//name spaces
using namespace std;
using namespace HASH;
using namespace someUsefull;
//end of name spaces
//defines
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define NO cout << "NO" << '\n';
#define YES cout << "YES" << '\n';
//end of defines
//debug defines
#ifdef HOME
#define debug(x) cout << #x << " " << x << endl;
#define debug_p(x) cout << #x << " " << x.ff << " " << x.ss << endl;
#define debug_v(x) {cout << #x << " "; for (auto ioi : x) cout << ioi << " "; cout << endl;}
#define debug_vp(x) {cout << #x << " "; for (auto ioi : x) cout << '[' << ioi.ff << " " << ioi.ss << ']'; cout << endl;}
#define debug_v_v(x) {cout << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cout << ioi2 << " "; cout << '\n';} cout << "*/" << #x << endl;}
int jjj;
#define wait() cin >> jjj;
#define PO cout << "POMELO" << endl;
#define OL cout << "OLIVA" << endl;
#define gen_clock(x) ll x = clock(); cout << "Clock " << #x << " created" << endl;
#define check_clock(x) cout << "Time spent in " << #x << ": " << clock() - x << endl; x = clock();
#define reset_clock(x) x = clock();
#define say(x) cout << x << endl;
#else
#define debug(x) 0;
#define debug_p(x) 0;
#define debug_v(x) 0;
#define debug_vp(x) 0;
#define debug_v_v(x) 0;
#define wait() 0;
#define PO 0;
#define OL 0;
#define gen_clock(x) 0;
#define check_clock(x) 0;
#define reset_clock(x) 0;
#define say(x) 0;
#endif // HOME
//end of debug defines
void solve() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; ++i)
cin >> arr[i];
vector<ll> dp(3е5);
vector<int> canbe(3e5, 0);
vector<ll> dp2(3e5);
dp[0] = 1;
dp2[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = dp.size() - 1; j >= arr[i]; --j) {
Hplus(dp[j], dp[j - arr[i]]);
Hplus(dp2[j], dp2[j - arr[i]], modfft);
}
}
int ma = 0;
for (int j = dp.size() - 1; j > 0; --j)
if (dp[j] || dp2[j]) {
ma = j;
break;
}
if (ma & 1) {
cout << 0;
return;
}
if (dp[ma >> 1] == 0 && dp2[ma >> 1] == 0) {
cout << 0;
return;
}
for (int i = 0; i < n; ++i) {
if (i != -1) {
for (int j = arr[i]; j < dp.size(); ++j) {
Hminus(dp[j], dp[j - arr[i]]);
Hminus(dp2[j], dp2[j - arr[i]], modfft);
}
}
int ma = 0;
for (int i = dp.size() - 1; i > 0; --i) {
if (dp[i] || dp2[i]) {
ma = i;
break;
}
}
debug(i);
//vector<int> opa(dp.begin(), dp.begin() + ma + 1);
//debug_v(opa);
debug(ma);
for (int i = 0; i * 2 <= ma; ++i) {
if (dp[i] || dp2[i]) {
debug(i);
debug(ma - i - i);
++canbe[ma - i - i];
}
}
if (i != -1) {
for (int j = dp.size() - 1; j >= arr[i]; --j) {
Hplus(dp[j], dp[j - arr[i]]);
Hplus(dp2[j], dp2[j - arr[i]], modfft);
}
}
}
vector<int> ans;
for (int i = 0; i < dp.size(); ++i) {
if (canbe[i] == n) {
ans.push_back(i);
}
}
cout << ans.size() << '\n';
for (int i : ans)
cout << i << " ";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
t = 1;
// cin >> t;
for (int i = 0; i < t; ++i) {
solve();
cout << '\n';
}
return 0;
}
/*
5
3 2
3 -2
-2 -2
-2 2
0 0
*/