제출 #1176634

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176634		t_danh	Bank (IZhO14_bank)	C++20	100 / 100	100 ms	8592 KiB

bank

// https://cses.fi/problemset/task/1653 
/*
 ██████████        ███████                       ██  
░░░░░██░░░        ░██░░░░██                     ░██  
    ░██           ░██    ░██   ██████   ███████ ░██  
    ░██           ░██    ░██  ░░░░░░██ ░░██░░░██░██████
    ░██           ░██    ░██   ███████  ░██  ░██░██░░░██
    ░██           ░██    ██   ██░░░░██  ░██  ░██░██  ░██
    ░██     █████ ░███████   ░░████████ ███  ░██░██  ░██
    ░░     ░░░░░  ░░░░░░░     ░░░░░░░░ ░░░   ░░ ░░   ░░
*/
 
#include <bits/stdc++.h>
#define input  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ce cout << endl
#define FOR(i, l, r) for (ll i = l; i <= r; i++)
#define FOR2(i, l, r) for (ll i = l; i >= r; i--)
using namespace std;
using ll = long long;
using str = string;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
 
const ll N = 1e5+1;
const ll LOGN = 19;
const int INF = numeric_limits<int>::max();
const ll MOD = 1e9 + 7;
ll dx[] = {1, -1, 0, 0};
ll dy[] = {0, 0, 1, -1};
void solve() {
    int n , m;
    cin >> n >> m;
    vector<int> A(n),B(m);
    FOR(i,0,n-1) cin >> A[i];
    FOR(i,0,m-1) cin >> B[i];
    vector<int> money_left( 1<<m,-1);
    vector<int> people_covered(1 << m , -1);
    money_left[0] = 0;
    people_covered[0] = 0;
    for(int mask = 0 ; mask < 1 << m ; mask ++){
        for(int last = 0 ; last < m ; last ++){
            if(!(mask & ( 1 << last))) continue;
            int prev = mask ^ (1 << last);
            if(people_covered[prev] == -1) continue;
            int cur_amount = money_left[prev] + B[last];
            int curr_target = A[people_covered[prev]];
            if(cur_amount == curr_target){
                people_covered[mask] = people_covered[prev] + 1;
                money_left[mask] = 0;
            }
            else if(cur_amount < curr_target){
                money_left[mask] = cur_amount;
                people_covered[mask] = people_covered[prev];
            }
        }
        if(people_covered[mask] == n){
            cout << "YES" <<endl;
            return;
        }
    }
    cout << "NO" <<endl;return;


}
 
int main() {
    input
    const bool cap = true;

    if (cap)
        solve();    
    else {
        ll t;
        cin >> t;
        while (t--) solve();
    }
}

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