제출 #1128036

#제출 시각아이디문제언어결과실행 시간메모리
1128036VietnowBootfall (IZhO17_bootfall)C++20
0 / 100
2 ms320 KiB
#include <bits/stdc++.h> #define yes cout<<"YES\n" #define no cout<<"NO\n" #define int long long #define ff first #define ss second #define pb push_back #define y1 zildjian #define left radio #define right head using namespace std; const int N = 3e5+10; const int INF = 1e18; const int mod = 1e9+7; const int mod1 = 998244353; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; int a[N]; int dp[N]; void solve(){ cin>>n; int sum = 0; for(int i = 1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } if(sum%2){ cout<<0; return; } for(int i = 2;i<=n;i++){ if(a[i]%2 != a[i-1]%2){ cout<<'0'; return; } } dp[0] = 1; for(int i = 1;i<=n;i++){ for(int w = sum;w>=1;w--){ dp[w] += dp[w-a[i]]; } } if(!dp[sum/2]){ cout<<0<<'\n'; return; } vector<int> v; for(int i = 1;i<=sum;i++){ // cout<<dp[i]<<' '; if(i%2 == a[1]%2){ v.pb(i); } } vector<int> ans; for(auto x:v){ bool ok = 1; // cout<<x<<'\n'; for(int i = 1;i<=n;i++){ for(int w = 0;w+a[i]<=sum;w++){ if(dp[w] && dp[w+a[i]]){ dp[w+a[i]] -= dp[w]; } } // cout<<i<<":\n"; for(int w = sum;w>=x;w--){ dp[w] += dp[w-x]; } // for(int w = 1;w<=sum/2;w++){ // cout<<dp[w]<<' '; // } // cout<<'\n'; if((sum-a[i]+x)%2 || !dp[(sum-a[i]+x)/2]){ ok = 0; for(int w = 0;w+x<=sum;w++){ if(dp[w] && dp[w+x]){ dp[w+x] -= dp[w]; } } for(int w = sum;w>=a[i];w--){ dp[w] += dp[w-a[i]]; } break; } for(int w = 0;w+x<=sum;w++){ if(dp[w] && dp[w+x]){ dp[w+x] -= dp[w]; } } for(int w = sum;w>=a[i];w--){ dp[w] += dp[w-a[i]]; } // for(int w = 1;w<=sum/2;w++){ // cout<<dp[w]<<' '; // } // cout<<'\n'; } if(ok){ ans.pb(x); } } // cout<<'\n'; cout<<ans.size()<<'\n'; for(auto x:ans) cout<<x<<' '; } signed main(){ freopen("bootfall.in","r",stdin); freopen("bootfall.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(nullptr); // cout.tie(nullptr); int t = 1; // cin>>t; for(int i = 1;i<=t;i++){ // cout<<"Case "<<i<<": "; solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

bootfall.cpp: In function 'int main()':
bootfall.cpp:112:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     freopen("bootfall.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     freopen("bootfall.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...