Submission #625505

#	Time	Username	Problem	Language	Result	Execution time	Memory
625505		NintsiChkhaidze	Bank (IZhO14_bank)	C++14	100 / 100	79 ms	8532 KiB

bank

#include <bits/stdc++.h>
// #define int long long
#define pb push_back
#define s second
#define f first
#define pii pair<int,int>
using namespace std;

const int N = 25;
int a[N],b[N],mx[(1<<21) + 5],extra[(1<<21) + 5];

signed main (){
    int n,m;
    cin>>n>>m;
    
    for (int i = 1; i <= n; i++)
        cin>>a[i];
        
    for (int i = 0; i < m; i++)
        cin>>b[i];
        
    for (int i = 0; i < (1<<m); i++) 
        mx[i] = -1;
    
    mx[0] = 0;
    for (int i = 0; i < (1<<m); i++){
        if (mx[i] == -1) continue;
        for (int j = 0; j < m; j++){
            if ((i&(1<<j))) continue;
            int current = extra[i] + b[j];
            int id = mx[i] + 1;
            
            if (a[id] == current){
                mx[i^(1<<j)] = mx[i] + 1;
                if (mx[i] + 1 == n){
                    cout<<"YES\n";
                    return 0;
                }
                extra[i^(1<<j)] = 0;
            }else if (current < a[id]){
                mx[i^(1<<j)] = mx[i];
                extra[i^(1<<j)] = current;
            }
        }
    }
    
    cout<<"NO";
}

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