제출 #1303626

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303626		zhen	은행 (IZhO14_bank)	C++17	100 / 100	97 ms	16864 KiB

bank

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // freopen("template.in", "r", stdin);
    // freopen("template.out", "w", stdout);
    
    ll n, m; cin >> n >> m;
    vector<ll> a(n), b(m); for (ll i = 0; i < n; ++i){cin >> a[i];} for (ll i = 0; i < m; ++i){cin >> b[i];}
    vector<ll> done(1 << m, -1); vector<ll> left(1 << m,  -1);
    done[0] = 0; left[0] = 0; 
    
    for (ll s = 1; s < (1 << m); ++s){
        for (ll i = 0; i < m; ++i){
            if (!(s & (1 << i))){continue;}
            ll k = s - (1 << i);
            if (left[k] + b[i] == a[done[k]]){
                if (done[k] > done[s]){
                    done[s] = done[k] + 1;
                    left[s] = 0;
                }
            }
            else {
                if (done[k] > done[s]){
                    done[s] = done[k];
                    left[s] = left[k] + b[i];
                }
            }
        }
        if (done[s] == n){
            cout << "YES"; return 0;
        }
    }
    cout << "NO";
}

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