제출 #1108920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1108920		julia_08	은행 (IZhO14_bank)	C++17	100 / 100	113 ms	8956 KiB

bank

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

const int MAXN = 22;

int a[MAXN], b[MAXN];

pair<int, int> dp[1 << MAXN]; // maximo prefixo, quanto ja paguei

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;

  for(int i=0; i<n; i++){
    cin >> a[i];
  }

  for(int i=0; i<m; i++){
    cin >> b[i];
  }

  for(int s=0; s<(1 << m); s++) dp[s] = {-1, 0};

  for(int s=0; s<(1 << m); s++){

    for(int i=0; i<m; i++){

      if(s & (1 << i)) continue;
      
      dp[s ^ (1 << i)] = max(dp[s ^ (1 << i)], dp[s]);

      if(a[dp[s].first + 1] - dp[s].second == b[i]){
        dp[s ^ (1 << i)] = max(dp[s ^ (1 << i)], {min(n - 1, dp[s].first + 1), 0});

      } else if(b[i] < a[dp[s].first + 1] - dp[s].second){
        dp[s ^ (1 << i)] = max(dp[s ^ (1 << i)], {dp[s].first, dp[s].second + b[i]});

      }

    }
    
    // cout << s << " " << dp[s].first << " " << dp[s].second << "\n";

  }

  cout << ((dp[(1 << m) - 1].first == n - 1) ? "YES" : "NO") << "\n";

  return 0;
}

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