Submission #1118251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118251		yazansh	Bank (IZhO14_bank)	C++17	100 / 100	92 ms	16892 KiB

bank

/*
this code written by :
shimutski_zoro
*/
#include <bits/stdc++.h> 
 
using namespace std; 
 
#define yon(x) cout<<((x)?"YES\n":"NO\n"); 
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend() 
#define ff first 
#define ss second 
#define em emplace 
#define emp emplace_back 
#define rep(i,j,k) for(int i=j;i<=k;i++) 
#define per(i,j,k) for(int i=k;i>=j;i--) 
#define forp(x,y,a) for(auto &[x,y]:(a)) 
typedef long long  ll; 
typedef pair<ll,ll> pll; 
typedef vector<ll> vl; 
typedef vector<pll> vpl; 
typedef vector<vl> vvl; 
typedef vector<vpl> vvpl; 
typedef vector<string> vs; 
typedef vector<set<ll> >vst;
typedef deque<ll> dl; 
const int mod=1e9+7;
const ll inf =1e18+1; 
const int N=1e6+1; 
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1}; 
void solve(){ 
ll n,x;
cin>>n>>x;
vl a(n);
vpl dp(1<<x,{-1,-1});
dp[0]={0,0};
rep(i,0,n-1){
    cin>>a[i];  
      }  
      vl b(x);
      rep(i,0,x-1){
    cin>>b[i];  
      }
      bool is=0; 
     rep(msk,0,((1<<x)-1)){
        rep(i,0,x-1){
            if(msk&(1<<i)||dp[msk].ff==-1)continue;
           if(dp[msk].ss<n&&dp[msk].ff+b[i]<=a[dp[msk].ss]){
            dp[msk|(1<<i)]=make_pair((dp[msk].ff+b[i]==a[dp[msk].ss])?0:dp[msk].ff+b[i],(dp[msk].ff+b[i]==a[dp[msk].ss])?dp[msk].ss+1:dp[msk].ss);
           }
         }  
         if(dp[msk].ss>=n){
            is=1;
         }
                                                                          
}
yon(is);
}
signed main() { 

    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    #ifdef Usaco 
    string f="guard"; 
    freopen((f+".in").c_str(),"r",stdin); 
    freopen((f+".out").c_str(),"w",stdout); 
    #endif 
    int t = 1; 
    //cin >> t; 
    while (t--) { 
        solve();  
    } 
} 
/* 
example:

*/

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