Submission #1091969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091969		ULTRABIG7	Bank (IZhO14_bank)	C++14	100 / 100	184 ms	17692 KiB

bank

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;

#define ff first
#define ss second
#define pb push_back
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i = (a);i<(b);i++)
#define F0R(i,a) FOR(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for(auto& a:x)
#define sz(x) (int)size(x)
#define vi vector<int>
const int MOD = 1e9+7;
const db PI = acos((db)-1);

const int N = (1<<20);
int n,m;
int dp[N], val[N];
bool vis[N];
int A[20],B[20], pref[20];


// dp[x] é o máximo de salários que aquela bitmask consegue cobrir
// dp[0] = 0 e dp[x] = -1 para todo resto:




int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    

    FOR(i,0,n){
        cin>>A[i];
    }

    pref[0] = A[0];
    FOR(i,1,n){
        pref[i] = pref[i-1]+A[i];
    }

    FOR(i,0,m){
        cin>>B[i];
    }

    queue<int> q;
    q.push(0);

    const int M = (1<<m);

    FOR(i,0,M){
        dp[i] = -1;

        FOR(bit,0,m){
            if((1<<bit)&i){
                val[i] += B[bit];
            }
        }
    }

    dp[0] = 0;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(vis[x]) continue;

        vis[x] = true;
        // dp[x] guarda o quanto ele já fez, então estamos preocupados com o próximo, ou seja, com o 
        // dp[x]-ésimo

        if(dp[x] == n){
            cout<<"YES\n";
            return 0;
        }

        int prox = dp[x];
        for(int bit = 0;bit<m;bit++){
            if((1<<bit)&x) continue;

            int novo = x^(1<<bit);

            // adicionamos o B[bit]
            if(val[novo] > pref[prox]){
                continue;
            }

            if(val[novo] == pref[prox]){
                dp[novo] = dp[x]+1;
                q.push(novo);
                continue;
            }

            if(val[novo] < pref[prox]){
                dp[novo] = dp[x];
                q.push(novo);
                continue;
            }
        }
    }


    cout<<"NO\n";

    /*FOR(i,0,M){
        cout<<i<<" "<<dp[i]<<"\n";
    }*/

    return 0;
}

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