Submission #1193705

#TimeUsernameProblemLanguageResultExecution timeMemory
1193705Hamed_Ghaffari은행 (IZhO14_bank)C++20
100 / 100
334 ms19524 KiB
#include <bits/stdc++.h>
using namespace std;

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ull = unsigned long long;

#define X               first
#define Y               second
#define SZ(x)           int(x.size())
#define all(x)          x.begin(), x.end()
#define mins(a,b)       (a = min(a,b))
#define maxs(a,b)       (a = max(a,b))
#define pb              push_back
#define Mp              make_pair
#define lc              id<<1
#define rc              lc|1
#define mid             ((l+r)>>1)
mt19937_64              rng(chrono::steady_clock::now().time_since_epoch().count());

const ll  INF = 1e9 + 23;
const ll  MOD = 1e9 + 7;
const int MXN = 2e5 + 5;
const int LOG = 23;

int n, m, a[20], b[20];
vector<int> msks[1001];
int sum[1<<20];
bool dp[20][1<<20];

void Main() {
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> a[i];
    for(int i=0; i<m; i++) cin >> b[i];
    int mxa = *max_element(a, a+n);
    for(int msk=1; msk<(1<<m); msk++) {
        sum[msk] = sum[msk^(msk&-msk)] + b[__lg(msk&-msk)];
        if(sum[msk]<=mxa) msks[sum[msk]].push_back(msk);
    }
    for(int msk : msks[a[0]]) dp[0][((1<<m)-1)^msk] = 1;
    for(int i=0; i+1<n; i++)
        for(int msk=0; msk<(1<<m); msk++)
            if(dp[i][msk])
            for(int msk2 : msks[a[i+1]])
                if((msk&msk2)==msk2)
                    dp[i+1][msk^msk2] = 1;
    cout << (*max_element(dp[n-1], dp[n-1]+(1<<m)) ? "YES" : "NO") << '\n';
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    int T = 1;
    // cin >> T;
    while(T--) Main();
    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...