제출 #1105195

#제출 시각아이디문제언어결과실행 시간메모리
1105195nh0902은행 (IZhO14_bank)C++14
19 / 100
77 ms5448 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1200000; int n, m, a[30], b[30], sum_a[30], sum_b[N]; bool dp[N][30]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for (int i = 1; i <= n; i ++) { cin >> a[i]; sum_a[i] = a[i] + sum_a[i - 1]; } for (int i = 1; i <= m; i ++) { cin >> b[i]; //cout << i << " : " << b[i] << "\n"; } if (n > m) { cout << "NO"; return 0; } int k = 1 << m; for (int i = 1; i < k; i ++) { for (int j = 0; j < m; j ++) { if ((i >> j) & 1) { sum_b[i] = sum_b[i - (1 << j)] + b[j + 1]; //cout << i << " , " << j << " " << b[j + 1] << " " << sum_b[i] << "\n"; break; } } } dp[0][0] = true; for (int i = 0; i <= n; i ++) { for (int j = 0; j < k; j ++) { if (dp[i][j]) { if (sum_a[i] == sum_b[j]) { dp[i + 1][j] = true; //cout << "check " << i << " , " << j << "\n"; } if (sum_a[i] > sum_b[j]) { for (int t = 0; t < m; t ++) { if (((j >> t) & 1) == 0) { if (sum_a[i] >= sum_b[j + (1 << t)]) { dp[i][j + (1 << t)] = true; } //cout << "new " << i << " , " << j << " , " << t << "\n"; } } } } } } bool yes = false; for (int i = 1; i < k; i ++) { if ((sum_a[n] == sum_b[i]) && dp[n][i]) { yes = true; //cout << i << " : " << sum_a[n] << " , " << sum_b[i] << "\n"; break; } } if (yes) { cout << "YES"; } else { cout << "NO"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...