Submission #1347626

#TimeUsernameProblemLanguageResultExecution timeMemory
1347626Rafael_AugustoBank (IZhO14_bank)C++20
100 / 100
123 ms16852 KiB
#include <bits/stdc++.h>
using namespace std;

// Muito cuidado por aqui ↓
#define int long long
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)

typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 20+7;
const int MAX = (1<<20)+7;

int a[MAXN], b[MAXN];
int sum[MAX], pf[MAXN];
int dp[MAX];

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);

    memset(dp, -1, sizeof dp);

    int n, m; cin >> n >> m;

    fall(i, 0, n) cin >> a[i];
    fall(i, 0, m) cin >> b[i];

    fall(mask, 0, (1<<m)){
        int s=0;

        fall(i, 0, m) if((1<<i)&mask) s += b[i];

        sum[mask]=s;
    }

    pf[0]=a[0];

    fall(i, 1, n) pf[i] = pf[i-1]+a[i];

    fall(mask, 0, (1<<m)){
        fall(i, 0, m) if((1<<i)&mask){
            int j = dp[mask-(1<<i)]+1;

            int rest = sum[mask]-(pf[j]-a[j]);

            dp[mask] = max(dp[mask], j-1+(rest == a[j]));
        }
    }

    cout << (dp[(1<<m)-1] == n-1 ? "YES" : "NO") << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...