제출 #752643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752643		I_love_Daneliya	은행 (IZhO14_bank)	C++17	19 / 100	157 ms	82388 KiB

bank

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

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