제출 #1001375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001375		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	124 ms	5548 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int a[25], b[25], sum[1 << 20];
bool dp[1 << 20];
inline bool getbit(int num, int bit)
{
    return (num >> bit)&1;
}
inline int flipbit(int num, int bit)
{
    return num ^ (1 << bit);
}
int main()
{
    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 i = 1; i < n; i++) a[i] += a[i-1];
    for(int i = 0; i < (1 << m); i++){
        for(int j = 0; j < m; j++) if(getbit(i, j) == 1) sum[i] += b[j];
    }
    dp[0] = 1;
    for(int i = 0; i < (1 << m); i++) if(dp[i] == 1){
        int re = *upper_bound(a+0, a+n, sum[i]) - sum[i];
        for(int j = 0; j < m; j++) if(getbit(i, j) == 0 && b[j] <= re) dp[flipbit(i, j)] = 1;
    }
    bool ok = 0;
    for(int i = 0; i < (1 << m); i++) if(dp[i] == 1 && sum[i] == a[n-1]){ok = 1; break;}
    if(ok == 1) cout<<"YES";
    else cout<<"NO";
}

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