제출 #658859

#제출 시각아이디문제언어결과실행 시간메모리
658859a_aguilo은행 (IZhO14_bank)C++14
71 / 100
1095 ms86356 KiB
#include<bits/stdc++.h> using namespace std; int main(){ cin.tie(NULL); ios::sync_with_stdio(false); int n, m; cin >> n >> m; int salaries[n]; int banknotes[m]; for(int i = 0; i < n; ++i) cin >> salaries[i]; for(int i = 0; i < m; ++i) cin >> banknotes[i]; int DP[1<<m][n+1]; memset(DP, -1, sizeof(DP)); DP[0][0] = 0; for(int mask = 1; mask < (1 << m); ++mask){ for(int note = 0; note < m; ++note){ if(mask&(1<<note)){ DP[mask][0] = DP[mask^(1<<note)][0] + banknotes[note]; } } //cout << DP[mask][0] << endl; } for(int person = 1; person <= n; ++person){ for(int mask = 1; mask < (1<<m); ++mask){ if(DP[mask][person-1] == salaries[person-1]) DP[mask][person] = 0; for(int note = 0; note < m; ++note){ if(mask&(1<<note)){ if(DP[mask^(1 << note)][person] != -1){ DP[mask][person] = DP[mask^(1<<note)][person]+banknotes[note]; } } } if((person == n) and (DP[mask][person] != -1)) { cout << "YES" << endl; return 0; } } } cout << "NO" << endl; 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...