Submission #848649

#	Time	Username	Problem	Language	Result	Execution time	Memory
848649		mariam197	Bank (IZhO14_bank)	C++17	100 / 100	364 ms	88940 KiB

bank

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
#define ll long long
#define ld long double
#define mod 1000000007
#define all(x) x.begin(),x.end()
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
vector<int> v[1005];
int n;
int a[20];
int dp[20][1 << 20];
bool solve(int i,int mask){
    if(i==n){
        return 1;
    }
    if(dp[i][mask]!=-1) return dp[i][mask];
    bool res=0;
    for(auto j: v[a[i]]){
        if((mask&j)==0){
            res|=solve(i+1,mask|j);
        }
    }
    return dp[i][mask]=res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    cin>>n>>m;
    vector<int> b(m);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    reverse(all(b));
    for(int mask=1;mask<(1<<m);mask++){
        ll sum=0;
        for(int i=0;i<m;i++){
            if((mask&(1<<i))){
                sum+=b[i];
            }
        }
        if(sum<=1000){
            v[sum].push_back(mask);
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<(solve(0,0)==1?"YES":"NO");
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool solve(int, int)':
bank.cpp:27:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |     return dp[i][mask]=res;
      |            ~~~~~~~~~~~^~~~

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