제출 #1205001

#제출 시각아이디문제언어결과실행 시간메모리
1205001sopaipillaBank (IZhO14_bank)C++20
100 / 100
236 ms127764 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n); int tot=0; for(int &x : a) { cin >> x; tot+=x; } sort(a.begin(),a.end()); vector<int> b(m); for(int &x : b) cin >> x; sort(b.begin(),b.end()); if(n>m) { cout << "NO"; return 0; } if(n==m) { if(a==b) cout << "YES"; else cout << "NO"; return 0; } vector<vector<int>> get(tot+1); get[0]={0}; for(int i=0; i<m; ++i) { for(int e=tot; e>=b[i]; --e) { for(int from : get[e-b[i]]) { if((from & (1<<i))) continue; get[e].pb((from|(1<<i))); } } } vector<vector<int>> dp((1<<m),vector<int>(n,0)); for(int mask : get[a[0]]) dp[mask][0]=1; for(int i=0; i<(n-1); ++i) { for(int mask=1; mask<(1<<m); ++mask) { if(!dp[mask][i]) continue; for(int proxmask : get[a[i+1]]) { if((mask & proxmask)) continue; dp[(mask|proxmask)][i+1]=1; } } } for(int mask=1; mask<(1<<m); ++mask) { if(dp[mask][n-1]) { cout << "YES"; return 0; } } cout << "NO"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...