제출 #1285303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285303		dobri_oke	은행 (IZhO14_bank)	C++20	100 / 100	100 ms	9096 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
//#define int long long

const int N = 1e6+100;
int n, m, a[21], b[21];
pair < int, int > dp[(1 << 20)];
void solve(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    for(int mask = 1; mask < (1 << m); mask++) dp[mask].F = dp[mask].S = -1;
    for(int mask = 0; mask < (1 << m); mask++){
        for(int i = 0; i < m; i++){
            if(((mask >> i) & 1) == 0) continue;
            if(dp[(mask ^ (1 << i))].F == -1) continue;
            mask = (mask ^ (1 << i));
            int f = dp[mask].F, s = dp[mask].S, need = a[f];
            mask = (mask | (1 << i));
            if(s + b[i] < need){
                dp[mask].F = f;
                dp[mask].S = s + b[i];
            }
            else if(s + b[i] == need){
                dp[mask].F = f + 1;
                dp[mask].S = 0;
            }
        }
        if(dp[mask].F == n){ 
            cout << "YES\n";
            return;   
        }
    }
    cout << "NO\n";
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

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