제출 #978349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978349		KasymK	은행 (IZhO14_bank)	C++17	100 / 100	106 ms	8664 KiB

bank

#include "bits/stdc++.h"

using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int &i : a)
        cin >> i;
    for(int &i : b)
        cin >> i;
    int ok = 0;
    vector<int> dp(1 << m, -1), dp2(1 << m, -1);
    dp[0] = 0, dp2[0] = 0;
    for(int mk = 0; mk < (1 << m); ++mk){
        for(int i = 0; i < m; ++i)
            if(mk >> i & 1)
                if(~dp2[(mk & ~(1 << i))]){
                    if(dp[(mk & ~(1 << i))] + b[i] < a[dp2[(mk & ~(1 << i))]])
                        dp2[mk] = dp2[(mk & ~(1 << i))], dp[mk] = dp[(mk & ~(1 << i))] + b[i];
                    else if(dp[(mk & ~(1 << i))] + b[i] == a[dp2[(mk & ~(1 << i))]])
                        dp2[mk] = dp2[(mk & ~(1 << i))] + 1, dp[mk] = 0;
                }
        ok |= (!(dp2[mk]^n));
    }
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

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