Submission #1229100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229100		nhathanh	Bank (IZhO14_bank)	C++20	100 / 100	93 ms	8644 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define el "\n"
#define fi first
#define se second
#define pii pair<int,int>
#define fre(NAME)        freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout)
int n,m;
int a[21],b[21];
int dp[(1<<20)-1][2];
string trans(int x)
{
   if(x==0) return "0";
   string temp;
   while(x>0)
   {
      temp+=char('0'+x%2);
      x/=2;
   }
      reverse(temp.begin(),temp.end());
   return temp;
}
signed main()
{
    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];
    for(int j=0;j<m;j++) cin>>b[j];
    memset(dp,-1,sizeof(dp));
    dp[0][0]=1;
    dp[0][1]=0;
    for(int i=1;i<(1<<m);i++)
    {
       for(int j=0;j<m;j++)
       {
          if(!((i>>j)&1)) continue;
          int prev = i^(1<<j);
          if(dp[prev][0]==-1) continue;
          int have=dp[prev][1]+b[j];
          int need=a[dp[prev][0]];
          //cout<<trans(prev)<<" "<<have<<" "<<need<<" "<<j<<el;
          if(have<need)
          {
            dp[i][0]=dp[prev][0];
            dp[i][1]=have;
          }
          else if(have==need)
          {
            dp[i][0]=dp[prev][0]+1;
            dp[i][1]=0;
          }
       }
       if(dp[i][0]==n+1)
       {
          cout<<"YES";
          return 0;
       }
    }
    cout<<"NO";
}

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