제출 #882802

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882802		skywwla	은행 (IZhO14_bank)	C++17	100 / 100	223 ms	86704 KiB

bank

#include <bits/stdc++.h>

using namespace std ;
using ll = long long ;

int32_t main() {
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    int n , m ; cin >> n >> m ;
    vector<ll> a(n), b(m) ;
    for (ll &i : a) cin >> i ;
    for (ll &i : b) cin >> i ;
    vector<vector<int>> dp(n, vector<int>(1 << m, -1)) ;
    function<bool(int,int)> solve = [&](int i, int mask) {
        if (i == n) return true ;
        if (~dp[i][mask]) return bool(dp[i][mask]) ;
        bool ret = false ;
        for (int j = 0 ; j < m ; j++) {
            if ((mask >> j & 1)) continue ;
            if (a[i] >= b[j]) {
                a[i] -= b[j] ;
                int nxti = i + (!a[i]) ;
                ret |= solve(nxti, mask | (1 << j)) ;
                a[i] += b[j] ;
            }
        }
        dp[i][mask] = ret ;
        return ret ;
    };
    cout << (solve(0, 0) ? "YES" : "NO") ;
    return 0 ;
}

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