Submission #715813

#	Time	Username	Problem	Language	Result	Execution time	Memory
715813		ktkerem	Bank (IZhO14_bank)	C++17	100 / 100	136 ms	33240 KiB

bank

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 5e5+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll n , m;std::vector<ll> ar , br;
ll dp[1ll << 21] , lo[1ll << 21];
void solve(){
  std::cin >> n >> m;
  ar.resize(n);br.resize(m);
  for(ll i = 0;n>i;i++){
    std::cin >> ar[i];
  }
  for(ll j = 0;m>j;j++){
    std::cin >> br[j];
  }
  std::memset(dp , -1 , sizeof(dp));
  std::memset(lo , -1 , sizeof(lo));
  lo[0] = dp[0] = 0;
  ll lm = (1ll << m);
  for(ll i = 0;lm>i;i++){
    for(ll j = 0;m>j;j++){
      if(!(i & (1ll << j))) continue;
      ll lst = i ^ (1ll << j);
      if(dp[lst] == -1) continue;
      ll nw = lo[lst] + br[j];
      ll cur = ar[dp[lst]];
      if(cur > nw){
        dp[i] = dp[lst];
        lo[i] = lo[lst] + br[j];
      }
      else if(cur == nw){
        dp[i] = dp[lst] + 1;
        lo[i] = 0;
      }
    }
    if(dp[i] == n){
      std::cout << "YES\n";
      return;
    }
  }
  std::cout << "NO\n";
  return;/**/
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

bank.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |

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