Submission #1001721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001721		concac	Bank (IZhO14_bank)	C++17	100 / 100	93 ms	16852 KiB

bank

#include <bits/stdc++.h>
#include<unordered_map>
#define PI acos(-1.0)
#define pll pair<ll, ll>
#define ll long long
#define ld long double
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define pll2 pair<ll,pair<ll,ll>>
#define bit(i,k) ((k>>i)&1)
#define pii pair<int,int>
#define int long long
using namespace std;
const long long mod = 998244353;
const ll inf = 1e9;
const ll maxN = (1<<20)+5;
ll a[20],b[20];
pll dp[maxN];
void solve()
{
    ll n,m;
    cin>>n>>m;
    dp[0]={-1,a[0]};
    for(int i=0;i<n;i++){
      cin>>a[i];
    }
    for(int i=0;i<m;i++){
      cin>>b[i];
    }
    for(int i=0;i<(1<<m);i++){dp[i]={-1,0};}

    ll idx;
    for(int mask=0;mask<(1<<m);mask++){
      for(int i=0;i<m;i++){
        if(!bit(i,mask)){
          ll nmask=mask^(1<<i);

          pll here=dp[mask];
          if(here.ff==n-1)continue;

          if(a[here.ff+1]-here.ss>b[i]){
            dp[nmask]=max(dp[nmask],{here.ff,here.ss+b[i]});
          }
          if(a[here.ff+1]-here.ss==b[i]){
            dp[nmask]=max(dp[nmask],{here.ff+1,0});
          }
        }
      }
    }
    for(int mask=0;mask<(1<<m);mask++){
      // cout<<dp[mask].ff<<" "<<dp[mask].ss<<'\n';
      if(dp[mask].ff==n-1){
        // cout<<mask<<'\n';
        cout<<"YES";return;}
    }
    cout<<"NO";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //  freopen("cover.inp", "r", stdin);
    // freopen("cover.out", "w", stdout);
    ll nhim = 1;
    // cin >> nhim;
    // cout<<nhim<<'\n';
    while (nhim--) {
        solve();
    }
}

Compilation message (stderr)

bank.cpp: In function 'void solve()':
bank.cpp:35:8: warning: unused variable 'idx' [-Wunused-variable]
   35 |     ll idx;
      |        ^~~

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