제출 #752643

#제출 시각아이디문제언어결과실행 시간메모리
752643I_love_Daneliya은행 (IZhO14_bank)C++17
19 / 100
157 ms82388 KiB
// Madi abi crush !
#include <bits/stdc++.h>
using namespace std ;

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int N = 1e5 + 1 ;

int n , m , a[20] , b[20] ;
ll pref[20] ;

int dp[20][(1 << 20) + 1] ;

// 1 5
// 8
// 4 2 5 1 3 

bool go(int i , int mask , ll cur) {
   if (cur == pref[i]) {
      i++ , dp[i][mask] = 1 ;
   }
   if (i >= n) {
      cout << "YES\n" ;
      exit(0) ;
   }
   if (~dp[i][mask]) return dp[i][mask] ;
   bool ans = 0 ;
   for (int j = 0;  j < m ; j++) {
      if ((mask >> j & 1) == 0) {
         ans = max(ans , go(i , (mask | (1 << j)) , cur + b[j])) ;
      }
   }
   dp[i][mask] = ans ;
   return ans ;
}

void solve() {
   memset(*dp, -1, sizeof(dp)) ;
   cin >> n >> m ;
   for (int i = 1 ; i <= n ; i++) {
      cin >> a[i - 1] ;
   }
   for (int i = 0 ; i < n ; i++) {
      if (i) pref[i] = pref[i - 1] ;
      pref[i] += a[i] ;
   }
   for (int i = 1 ; i <= m ; i++) {
      cin >> b[i - 1] ;
   }
   go(0,0,0) ;
      cout << "NO\n" ;
}

int main() {
   ios::sync_with_stdio(false) ;
   cin.tie(0) ;
   int test = 1 ;
   // cin >> test ;
   for (int i = 1 ; i <= test ; i++) {
      solve() ;
   }
   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...