Submission #457772

#TimeUsernameProblemLanguageResultExecution timeMemory
457772mariowongBootfall (IZhO17_bootfall)C++14
28 / 100
1084 ms524 KiB
#include <bits/stdc++.h> using namespace std; int ct[250005],n,a[505],sum; bool dp[250005],gg[250005],imp; vector <int> ans; int main() { ios::sync_with_stdio(false); cin >> n; for (int i=1;i<=n;i++){ cin >> a[i]; sum+=a[i]; } for (int i=0;i<=n;i++){ for (int j=1;j<=n*500;j++){ dp[j]=false; gg[j]=false; } dp[0]=true; for (int j=1;j<=n;j++){ if (j != i){ for (int k=j*500;k>=a[j];k--){ dp[k]=dp[k]|dp[k-a[j]]; } } } if (i == 0){ if (sum%2 == 1 || !dp[sum/2]) imp=true; continue; } for (int j=0;j<=n*500;j++){ if (dp[j] && !gg[max(j,sum-j-a[i])-min(j,sum-j-a[i])]){ ct[max(j,sum-j-a[i])-min(j,sum-j-a[i])]++; gg[max(j,sum-j-a[i])-min(j,sum-j-a[i])]=true; } } } for (int i=1;i<=n*500;i++){ if (ct[i] == n) ans.push_back(i); } if (imp){ cout << "0\n\n"; return 0; } cout << (int)ans.size() << "\n"; for (int i=0;i<ans.size();i++){ cout << ans[i] << " "; } cout << "\n"; return 0; }

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i=0;i<ans.size();i++){
      |               ~^~~~~~~~~~~
#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...