제출 #361905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361905		czhang2718	은행 (IZhO14_bank)	C++17	100 / 100	145 ms	8704 KiB

bank

#include "bits/stdc++.h"
using namespace std;

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()
#define pb push_back
#define f first
#define s second
#define nl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MOD = 1e9+7;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;

// dp[i][mask] := is it possible to cover first i requests with b_mask
// if leftover > 0- check dp[i][mask^(1<<j)] for all j in subset
// if leftover=0- check dp[i-1][mask^(1<<j)]

// too slow..

// dp[mask]=max prefix length that can be covered WITH LEFTOVER < next a_i

int n, m;
int a[20];
int b[20];
int ps[20];
int sum[1048576];
int dp[1048576];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // freopen("input.txt", "r", stdin); 
  // freopen("output.txt", "w", stdout);

  cin >> n >> m;
  rep(i, 0, n-1) cin >> a[i];
  rep(j, 0, m-1) cin >> b[j];

  rep(i, 0, n-1){
    ps[i]=(i?ps[i-1]:0)+a[i];
  }

  rep(i, 1, (1<<m)-1){
    rep(j, 0, m-1){
      if(i&(1<<j)){
        if(sum[i]==0) sum[i]=sum[i^(1<<j)]+b[j];
        int x=dp[i^(1<<j)];
        int r=sum[i^(1<<j)]-(x==0?0:ps[x-1]);
        if(r+b[j]>a[x]) continue;
        if(r+b[j]==a[x]) dp[i]=max(dp[i], x+1);
        else dp[i]=max(dp[i], x);
      }
    }
    if(dp[i]==n){
      cout << "YES"; return 0;
    }
  }
  cout << "NO";
}

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