Submission #734722

#	Time	Username	Problem	Language	Result	Execution time	Memory
734722		Qwesz	Bank (IZhO14_bank)	C++14	100 / 100	114 ms	8512 KiB

bank

#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;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29