제출 #887366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887366		happypotter127	은행 (IZhO14_bank)	C++17	71 / 100	1008 ms	32360 KiB

bank

#include<bits/stdc++.h>
  using namespace std;
  bool dp[(1 << 20)+1][21];
  long long res[(1 << 21)];
  bool ok = false;
  long dept[50], money[50], pre[50], n, m;
  int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    cin >> n >> m;
    for(long i = 1; i <= n; i++){
      cin >> dept[i];
      pre[i] = pre[i-1] + dept[i];
    }
    for(long i = 0; i < m; i++)  cin >> money[i];

    for(long i = 0; i < (1 << m); i++){
      dp[i][0] = true;
      for(long p = 0; p < m; p++){
        if(i & (1 << p)){
          res[i] = res[i] + money[p];
        }
      }
    }
    for(long i = 1; i <= n; i++){
      for(long j = 0; j < (1 << m); j++){
        for(long p = 0; p < m; p++){
          if(!(j & (1 << p))){
            long u = j | (1 << p);
            if(dp[j][i] == true){
              dp[u][i] = true;
              if(i == n)  ok = true;
            }
            if(dp[j][i-1] == true){
              if(res[u] - pre[i-1] == dept[i]){
                dp[u][i] = true;
                if(i == n)  ok = true;
              }
            }
          }
        }
      }
    }
    if(ok == true)  cout << "YES";
    else            cout << "NO";
}

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