# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
697025 | 2023-02-08T00:04:53 Z | allllekssssa | Bootfall (IZhO17_bootfall) | C++14 | 1 ms | 724 KB |
#include<bits/stdc++.h> #pragma unroll using namespace std; const int maxN = 500 + 5; const int bsSize = (maxN * maxN + 10) / 2; int n; int a[maxN]; int cnt[maxN]; bitset<bsSize> dp[2][maxN], pre; int main() { cin >> n; //n = 500; int sum = 0; int gc = 0; for (int i = 1; i<=n; i++) { cin >> a[i]; // a[i] = min(2*i - 1, 499); gc = __gcd(a[i], gc); } sort(a + 1, a + n + 1); for (int i = 1; i<=n; i++) { a[i]/=gc; if ((a[i] & 1) == 0) { printf("0\n"); return 0; } if (cnt[a[i]] == 0) cnt[a[i]] = i; sum+=a[i]; } if (sum & 1) { printf("0\n"); return 0; } for (int i = 1; i <= n + 1; i++) { dp[0][i].set(0); } for (int i = 1; i<=n; i++) { bool updated = false; for (int j = 1; j <= n + 1; j++) { if (j<= n && cnt[a[j]] != j) continue; if (i == j) { dp[i&1][j] = dp[(i&1) ^ 1][j]; } else { if (updated) { dp[i&1][j] = pre; } else { dp[i&1][j] = dp[(i&1) ^ 1][j] | (dp[(i&1) ^ 1][j] << a[i]); if (i < j && !updated) { pre = dp[i&1][j]; updated = true; } } } } } if (dp[n&1][n + 1][sum/2] == 0) { printf("0\n"); return 0; } vector<int> ans; for (int i = 1; i <= sum; i+=2) { bool ok = true; for (int j = 1; j<= n; j++) { if (cnt[a[j]] != j) continue; int totSum = sum - a[j] + i; if (totSum % 2 == 1) ok = false; int val = totSum/2 - i; if (dp[n&1][j][val] == 0) ok = false; } if (ok) ans.push_back(i); } cout << ans.size() << endl; for (int i:ans) { cout << i * gc << " "; } cout << endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 724 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 724 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 724 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 724 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 724 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 1 ms | 724 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |