Submission #700108

#TimeUsernameProblemLanguageResultExecution timeMemory
700108messiuuuuuBootfall (IZhO17_bootfall)C++17
65 / 100
1030 ms3072 KiB
/// #include<bits/stdc++.h> #define task "C" #define ll long long #define ld long double #define fi first #define se second #define pb push_back using namespace std; const int MAXN = 5e2 + 5; const ll INF = 1e18 + 5; const int MOD = 1e9 + 22071997; int n; int a[MAXN], sum = 0; void Input() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } } int dp[MAXN * MAXN], chk[MAXN * MAXN]; void add(int& a, int b) { a += b; if (a >= MOD) a -= MOD; if (a < 0) a += MOD; } void Solve() { if (sum % 2) { cout << 0; return; } dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = sum; j >= a[i]; j--) { add(dp[j], dp[j - a[i]]); } } if (!dp[sum / 2]) { cout << 0; return; } for (int i = 1; i <= n; i++) { for (int j = a[i]; j <= sum; j++) { add(dp[j], -dp[j - a[i]]); } for (int j = 0; j <= sum; j++) { if ((sum + j - a[i]) & 1) continue; chk[j] += dp[(sum + j - a[i]) / 2] > 0; } for (int j = sum; j >= a[i]; j--) { add(dp[j], dp[j - a[i]]); } } vector<int> res; for (int i = 0; i <= sum; i++) if (chk[i] == n) res.pb(i); cout << res.size() << '\n'; for (int id : res) cout << id << ' '; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); if (fopen(task".INP","r")) { freopen(task".INP","r",stdin); //freopen(task".OUT","w",stdout); } Input(); Solve(); }

Compilation message (stderr)

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