Submission #1118296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118296		dosts	Bank (IZhO14_bank)	C++17	100 / 100	217 ms	16868 KiB

bank

//Dost SEFEROĞLU
#include <bits/stdc++.h>
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e18,MOD = 1e9+7;

int add(int x,int y) {
  return ((x+y) >= MOD ? x+y-MOD : x+y);
}
int mult(int x,int y) {
  return ((x*y)%MOD);
}

void solve() {
  int n,m;
  cin >> n >> m;
  vi a(n+1),b(m);
  for (int i=1;i<=n;i++) cin >> a[i];
  for (int i=0;i<m;i++) cin >> b[i];
  int lim = (1<<m);
  pii dp[lim];
  for (int i=0;i<lim;i++) dp[i] = {-inf,0};
  dp[0] = {0,0};
  for (int i=0;i<lim;i++) {
    if (dp[i].ff == -inf) continue;
    int cur = a[dp[i].ff+1];
    int rem = cur-dp[i].ss;
    for (int j = 0;j<m;j++) {
      dp[i|(1<<j)] = max(dp[i|(1<<j)],dp[i]);
    }
    for (int j = 0;j<m;j++) {
      if (i&(1<<j)) continue;
      if (b[j] > rem) continue;
      if (rem == b[j]) {
        dp[i|(1<<j)] = max(dp[i|(1<<j)],pii{dp[i].ff+1,0});
      } else dp[i|(1<<j)] = max(dp[i|(1<<j)],pii{dp[i].ff,dp[i].ss+b[j]});
    }
  }
  cout << ((dp[lim-1].ff == n) ? "YES\n" : "NO\n");
}                    
                             
int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);/* 
    #else 
      freopen("guard.in","r",stdin);
      freopen("guard.out","w",stdout); */
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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