Submission #467773

#TimeUsernameProblemLanguageResultExecution timeMemory
467773quocnghia32Bank (IZhO14_bank)C++14
100 / 100
143 ms16840 KiB
#include <bits/stdc++.h>
#define TASK "Bank"
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define READFILE freopen(TASK".INP","r",stdin)
#define WRITEFILE freopen(TASK".OUT","w",stdout)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define ENDL '\n'
#define debug(x) cout<<#x<<" = "<<x<<ENDL
#define fi first
#define se second
#define ever (;true;)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)(a).size())
#define ms(a,x) memset(a,x,sizeof(a))
#define int long long

using namespace std;
typedef vector <int> vi;
typedef pair <int,int> ii;
typedef vector <ii> vpi;
typedef pair <int,ii> iii;
const int N = 25;
const int oo=0x3f;
const int mod=1e9+7;
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
int a[N], cost[N], trace[(1<<20)+5], b[N];
ii dp[(1<<20)+5];
void init(){
  FAST;
}
bool cmp(ii a, ii b){
    return (a.fi<b.fi || a.fi==b.fi && a.se<b.se);
}
void tracee(int mask){
    b[trace[mask]-1]=1;
    if (trace[mask]!=0) tracee(trace[mask]);
}
signed main()
{
  init();
    int n,m;
    cin >> n >> m;
    For(i,0,n-1) cin >> a[i];
    For(i,0,m-1) cin >> cost[i];
    int mm=1<<m;
    for (int mask=0; mask<mm; mask++){
        For(i,0,m-1){
            if ((mask>>i)&1){
                ii p=dp[mask^(1<<i)];
                if (p.se+cost[i]==a[p.fi]){
                    {
                        dp[mask]={p.fi+1,0};

                    }
                }
                else dp[mask]=max(dp[mask],{p.fi,p.se+cost[i]});
            }
        }
    }
    if (dp[mm-1].fi==n) {
        cout << "YES" ;
    } else cout << "NO";
  return 0;
}

Compilation message (stderr)

bank.cpp: In function 'bool cmp(ii, ii)':
bank.cpp:35:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   35 |     return (a.fi<b.fi || a.fi==b.fi && a.se<b.se);
      |                                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...