Submission #1166377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166377		Richard_Dyinman	Bank (IZhO14_bank)	C++20	100 / 100	310 ms	52712 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using ordered_set =
        tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define file \
  freopen("guard.in", "r", stdin);\
  freopen("guard.out", "w", stdout)

#define OJudge(in,out) \
      freopen(in, "r", stdin);\
      freopen(out, "w", stdout)


#define FIn   \
  cin.tie(0); \
  cout.tie(0); \
  ios_base::sync_with_stdio(false)

const string IN = "input.txt";
const string OUT = "output.txt";
int  tc;
ll n,m,k,a,b,c;
bool dp[(1ll<<20) + 3][23];
bool vis[(1ll<<20) + 3][23] = {};
int arr[23], mon[23];
map<int, vector<int>> mp;

bool rec(int mask, int gay){
    if(gay == n){
        return 1;
    }
    if(mask == (1ll<<m) - 1)
        return 0;
    if(vis[mask][gay])
        return dp[mask][gay];
    vis[mask][gay] = 1;
    bool &ret = dp[mask][gay];
    ret = 0;
    if(!mp.count(arr[gay]))
        return 0;
    for(auto s : mp[arr[gay]]){
        if(!(s & mask)){
            ret |= rec(mask | s , gay + 1);
            if(ret)
                return ret;
        }
    }
    return ret;
}

void solve(){
    cin>>n>>m;
    for(int i = 0; i < n; i++){
        cin>>arr[i];
    }
    for(int i = 0; i < m; i++){
        cin>>mon[i];
    }
    for(int i = 1; i <(1ll<<m); i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            if((1ll<<j) & i){
                sum += mon[j];
            }
        }
        mp[sum].push_back(i);
    }
    cout<<(rec(0 , 0) ? "YES\n" : "NO\n");
}

int main() {
    FIn;
//    file;
//#ifndef ONLINE_JUDGE
//    OJudge(IN.c_str(),OUT.c_str());
//#endif
    bool test = 0;
    if (test)
        cin>>tc;
    else tc = 1;
    for (int i = 1; i<=tc; i++){
        solve();
    }
}

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