Submission #923027

#TimeUsernameProblemLanguageResultExecution timeMemory
923027penguin133Bootfall (IZhO17_bootfall)C++17
28 / 100
1075 ms38996 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pi pair<int, int> #define pii pair<int, pi> #define fi first #define se second #ifdef _WIN32 #define getchar_unlocked _getchar_nolock #endif mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); bitset <501*501*2>dp[505], dp2[505]; int n, A[505]; const int os = 500 * 500; bool chk(int a, int b){ if(os - a - b >= 0 && dp[n & 1][os - a - b])return 1; if(os - a + b >= 0 && os - a + b <= 2 * os && dp[n & 1][os - a + b])return 1; if(os + a - b >= 0 && os + a - b <= 2 * os && dp[n & 1][os + a - b])return 1; if(os + a + b <= 2 * os && dp[n & 1][os + a + b])return 1; return 0; } void solve(){ cin >> n; for(int i = 1; i <= n; i++)cin >> A[i]; //for(int i = 0; i <= 2 * os; i++)dp[0][i] = 0 dp[0][os] = dp2[n + 1][os] = 1; for(int i = 1; i <= n; i++){ dp[i] |= (dp[i - 1] >> A[i]); dp[i] |= (dp[i - 1] << A[i]); } for(int i = n; i >= 1; i--){ dp2[i] |= (dp2[i + 1] >> A[i]); dp2[i] |= (dp2[i + 1] << A[i]); } if(!dp[n][os]){ cout << 0; return; } set <int> s; for(int i = 1; i <= os; i++)s.insert(i); for(int i = 1; i <= n; i++){ /* bitset <501*501*2> tmp = dp[i - 1], tmp2; for(int j = 0; j <= os; j++){ if(dp2[i + 1][os - j] || dp2[i + 1][os + j]){ if(1)tmp2 |= (tmp >> j), tmp2 |= (tmp << j); } } */ bitset <501 * 501 * 2> tmp; tmp[os] = 1; for(int j = 1; j <= n; j++){ if(j == i)continue; tmp = (tmp >> A[j]) | (tmp << A[j]); } for(int j = 0; j <= os; j++)if(!tmp[os - j] && !tmp[os + j])s.erase(j); } cout << (int)s.size() << '\n'; for(auto i : s)cout << i << ' '; } main(){ ios::sync_with_stdio(0);cin.tie(0); int tc = 1; //cin >> tc; for(int tc1=1;tc1<=tc;tc1++){ // cout << "Case #" << tc1 << ": "; solve(); } }

Compilation message (stderr)

bootfall.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...