Submission #843867

#	Time	Username	Problem	Language	Result	Execution time	Memory
843867		Elvin_Fritl	Bank (IZhO14_bank)	C++17	100 / 100	106 ms	8816 KiB

bank

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

const int N = 25;

vector<int>a(N),b(N);

int n,m,ind[1<<20];
vector<int>dp((1<<20) , -1);

int32_t main()
{

    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    dp[0] = 0;
    for(int mask=0;mask<(1<<m);mask++){
        for(int i=0;i<m;i++){
            if(mask&(1<<i)){
                if(dp[mask ^ (1 << i)] == -1){
                    continue;
                }
                int cur = a[dp[mask ^ (1<<i)]] , r = ind[mask ^ (1<<i)];
                if(r + b[i] < cur){
                    dp[mask] = dp[mask ^ (1<<i)];
                    ind[mask] = r + b[i];
                }
                else if(r + b[i] == cur){
                    dp[mask] = dp[mask ^ (1<<i)] + 1;
                    ind[mask] = 0;
                }
                if(dp[mask] == n){
                    cout << "YES";
                    return 0;
                }
            }
        }
    }
    cout<<"NO\n";

    return 0;
}
/*

1 1    2 2    3 3    4 4
1


*/

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