Submission #1103584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103584		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	130 ms	7320 KiB

bank

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

#define ll long long

typedef pair<int,int> pii;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
#define f first
#define s second

#define all(x) x.begin(),x.end()
#define unicorn(x) x.resize(unique(x.begin(),x.end())-x.begin())

#define pb(x) push_back(x)
#define pp() pop_back()

#define lc id<<1
#define rc lc|1

const int L = 2e6+10;
const int inf = 1e9+10;
int n,m;
int dp[L],ps[L],a[L],b[L];

random_device device;
default_random_engine rng(device());
#define randt(a,b) uniform_int_distribution<int64_t>(a,b)(rng)

void pr(int* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void pr(long long* vv,int l,int r){for(int i=l;i<r;i++){cout<<vv[i]<<" ";}cout<<endl;}
void pr(pii* vv,int l,int r){for(int i=l;i<r;i++){cout<<i<<": "<<vv[i].f<<" , "<<vv[i].s<<" / ";}cout<<endl;}
void pr(vector<int> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void pr(vector<long long> vv){for(auto i:vv){cout<<i<<" ";}cout<<endl;}
void pr(vector<pii> vv){for(auto i:vv){cout<<i.f<<" , "<<i.s<<" / ";}cout<<endl;}

string bi(int a){
    for(int i=0;i<m;i++){
        cout<<((a&(1<<i)) > 0);
    }
    return "";
}

int main(){
    //ofstream cout ("out.txt");
    //ifstream cin ("in.txt");

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ps[i] = ps[i-1]+a[i];
    }
    //pr(ps,0,n+1);
    for(int i=0;i<m;i++){
        cin>>b[i];
    }
    dp[0] = 0;
    for(int mask=1;mask<(1<<m);mask++){
        ll sum = 0;
        for(int i=0;i<m;i++){
            if((mask&(1<<i)) > 0)
                sum += b[i];
        }

        for(int i=0;i<m;i++){
            if((mask&(1<<i)) == 0)
                continue;
            int mask2 = mask - (1<<i);
            dp[mask] = max(dp[mask],dp[mask2]+(sum == ps[dp[mask2]+1]));
        }
        //cout<<bi(mask)<<" --> "<<sum<<"  "<<dp[mask]<<endl;
    }
    //cout<<dp[(1<<m)-1]<<endl;
    if(dp[(1<<m)-1] == n){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

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