Submission #1091964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091964		ULTRABIG7	Bank (IZhO14_bank)	C++14	25 / 100	1103 ms	108040 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];
int A[20],B[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];
    }


    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;
    }

    dp[0] = 0;

    while(!q.empty()){
        int x = q.front();
        q.pop();

        // 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]

            int sum_atual = 0;
            FOR(i,0,m){
                if(novo&(1<<i)){
                    sum_atual += B[i];
                }
            }

            int cur = 0;
            FOR(i,0,prox+1){
                cur += A[i];
            }

            if(sum_atual > cur){
                continue;
            }

            if(sum_atual == cur){
                dp[novo] = dp[x]+1;
                q.push(novo);
                continue;
            }

            if(sum_atual < cur){
                dp[novo] = dp[x];
                q.push(novo);
                continue;
            }
        }
    }


    cout<<"NO\n";

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

    return 0;
}

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