제출 #734727

#제출 시각아이디문제언어결과실행 시간메모리
734727QweszBank (IZhO14_bank)C++14
100 / 100
104 ms8512 KiB
#include <iostream>
#include <vector>
#include <utility>
using namespace std;

bool pool = true;
int n, m, inp[20], bank[20];

int main(){
   cin >> n >> m;
   for(int i = 0; i < n; i++) cin >> inp[i];
   for(int i = 0; i < m; i++) cin >> bank[i];
   vector<pair<int, int>> dp(1 << m, {-1, 0});
   dp[0] = {0, 0};
   for(int i = 1; i < (1 << m); i++){
       for(int j = 0; j < m; j++){
           if(i & (1 << j)){
               int l = i ^ (1 << j),
               fir = dp[l].first,
               sec = dp[l].second;
               if(sec + bank[j] > inp[fir]) continue;
               else if(sec + bank[j] == inp[fir]){
                   fir++; sec = 0;
               }
               else sec += bank[j];
               dp[i] = max(dp[i], {fir, sec});
           }
       }
       if(dp[i].first == n){
           cout << "YES" << endl;
           //cout << i << endl;
           pool = false;
           break;
       }
   }
   if(pool) cout << "NO" << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...