제출 #978349

#제출 시각아이디문제언어결과실행 시간메모리
978349KasymKBank (IZhO14_bank)C++17
100 / 100
106 ms8664 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...