# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
171932 | 2019-12-30T16:25:49 Z | davitmarg | 은행 (IZhO14_bank) | C++17 | 102 ms | 14584 KB |
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() using namespace std; const int N = 25; int n, m, dp[N][(1 << 20) + 5]; int a[N], b[N], sum[(1 << 20) + 5]; vector<int> masks[N * 1003]; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) cin >> b[i]; for (int mask = 0; mask < (1 << m); mask++) { for (int i = 0; i < m; i++) if (((1 << i) & mask)) sum[mask] += b[i + 1]; masks[sum[mask]].PB(mask); //cout << mask << " = " << sum[mask] << endl; } dp[0][0] = 1; LL pr = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < masks[a[i]].size(); j++) { int mask = masks[a[i]][j]; for (int x = 0; x < masks[pr].size(); x++) { int s = masks[pr][x]; if (dp[i - 1][s]) dp[i][mask | s] = 1; } } //for (int mask = 0; mask < (1 << m); mask++) // cout << i << " : " << mask << " = " << dp[i][mask] << endl; pr += a[i]; } int ans = 0; for (int mask = 0; mask < (1 << m); mask++) ans += dp[n][mask]; if (ans) cout << "YES" << endl; else cout << "NO" << endl; return 0; } /* 2 4 9 10 5 4 5 5 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 888 KB | Output is correct |
2 | Correct | 2 ms | 888 KB | Output is correct |
3 | Correct | 3 ms | 1016 KB | Output is correct |
4 | Correct | 5 ms | 1400 KB | Output is correct |
5 | Correct | 101 ms | 11512 KB | Output is correct |
6 | Correct | 3 ms | 1016 KB | Output is correct |
7 | Correct | 3 ms | 888 KB | Output is correct |
8 | Correct | 102 ms | 14584 KB | Output is correct |
9 | Correct | 100 ms | 10872 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1016 KB | Output is correct |
2 | Correct | 2 ms | 888 KB | Output is correct |
3 | Correct | 3 ms | 888 KB | Output is correct |
4 | Incorrect | 3 ms | 1016 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 1272 KB | Output is correct |
2 | Correct | 4 ms | 1272 KB | Output is correct |
3 | Correct | 5 ms | 1272 KB | Output is correct |
4 | Correct | 4 ms | 1144 KB | Output is correct |
5 | Correct | 4 ms | 1144 KB | Output is correct |
6 | Correct | 5 ms | 1144 KB | Output is correct |
7 | Correct | 4 ms | 1276 KB | Output is correct |
8 | Correct | 4 ms | 1272 KB | Output is correct |
9 | Correct | 4 ms | 1144 KB | Output is correct |
10 | Correct | 5 ms | 1272 KB | Output is correct |
11 | Correct | 4 ms | 1016 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 888 KB | Output is correct |
2 | Correct | 2 ms | 888 KB | Output is correct |
3 | Correct | 3 ms | 1016 KB | Output is correct |
4 | Correct | 5 ms | 1400 KB | Output is correct |
5 | Correct | 101 ms | 11512 KB | Output is correct |
6 | Correct | 3 ms | 1016 KB | Output is correct |
7 | Correct | 3 ms | 888 KB | Output is correct |
8 | Correct | 102 ms | 14584 KB | Output is correct |
9 | Correct | 100 ms | 10872 KB | Output is correct |
10 | Correct | 3 ms | 1016 KB | Output is correct |
11 | Correct | 2 ms | 888 KB | Output is correct |
12 | Correct | 3 ms | 888 KB | Output is correct |
13 | Incorrect | 3 ms | 1016 KB | Output isn't correct |
14 | Halted | 0 ms | 0 KB | - |