Submission #442608

#	Time	Username	Problem	Language	Result	Execution time	Memory
442608		leaked	Bank (IZhO14_bank)	C++14	19 / 100	1 ms	320 KiB

bank

#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define vec vector
#define sz(x) ( int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
auto rng=bind(uniform_int_distribution<int>(1,32000),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=1e3+1;
bitset<N>emp,my,pref[N];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    vec<int>a(n),b(m);
    for(auto &z : a)
        cin>>z;
    for(auto &z : b)
        cin>>z;
    for(int i=0;i<n;i++){
        /// now we need to do
        my&=emp;my[0]=1;
        vec<int>nb;
        m=sz(b);
        for(int j=0;j<m;j++){
            pref[j]=my;
            my|=(my<<b[j]);
        }
        int s=a[i];
        if(!my[s]){
            cout<<"NO";
            return 0;
        }
        for(int j=m-1;j>=0;j--){
            if(s>=b[j] && pref[j][s-b[j]]) s-=b[j];
            else nb.pb(b[j]);
        }
        swap(b,nb);
    }
    cout<<"YES";
    return 0;
}

/*
4 4
1100
1110
0011
0011
*/

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