제출 #1140955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140955		O_Elmasry	은행 (IZhO14_bank)	C++20	52 / 100	1095 ms	13740 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif
#define endl '\n'
// #define int int64_t
#define int short int
const long long mod = 1000000007, MaxN = 200005, INF = 1e18;
int cur, N, M;
void rec(int idx, vector<int> &ret, int rest){
  if(idx == M){
    ret.push_back(cur);
    return;
  }
  rec(idx + 1, ret, rest);
  if(!((rest >> idx) & 1)){
    cur |= (1ll << idx);
    rec(idx + 1, ret, rest);
    cur ^= (1ll << idx);
  }
}
vector<int>generate(int submask){
  cur = 0;
  vector<int>ret;
  rec(0, ret, submask);
  return ret;
}
void solve(){
  int Max = 0;
  cin >> N >> M;
  vector<int>a(N), b(M);
  for(int i = 0;i < N;i++){
    cin >> a[i];
    Max = max(Max, a[i]); 
  }
  for(int i = 0;i < M;i++)cin >> b[i];
  vector<vector<int>>subsets(Max + 1);
  for(int mask = 1;mask < (1ll << M);mask++){
    int sum = 0;
    for(int i = 0;i < M;i++){
      if((mask >> i) & 1)sum += b[i];
    }
    if(sum <= Max)subsets[sum].push_back(mask);
  }
  vector<int>dp(1ll << M);
  dp[0] = 1;
  for(int i = 0;i < N;i++){
    vector<int>new_dp(1ll << M);
    for(auto submask : subsets[a[i]]){
      int bits = __builtin_popcountll(submask);
      auto ok = generate(submask);
      for(auto submask2 : ok){
        int mask = submask | submask2;
        new_dp[mask] |= dp[submask2];
      }
    }
    dp = new_dp;
  }
  int res = 0;
  for(auto x : dp)res |= x;
  cout << (res ? "YES" : "NO") << endl;
}
signed main()
{
#ifdef LOCAL
  FileRedirect("test");
#endif
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
  // freopen("pails.in","r",stdin);
  // freopen("pails.out","w",stdout);
  int Tc = 1;
  // cin >> Tc;
  for(int T = 1;T <= Tc;T++)solve();
}

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