Submission #922894

#TimeUsernameProblemLanguageResultExecution timeMemory
922894penguin133Bootfall (IZhO17_bootfall)C++17
13 / 100
1052 ms20788 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); } } if(i == 2){ //for(int j = 0; j <= os * 2; j++)if(tmp2[j])cout << j - os << ' '; //cout << '\n'; } for(int j = 0; j <= os; j++)if(!tmp2[os - j] && !tmp2[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:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | 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...