제출 #1001375

#제출 시각아이디문제언어결과실행 시간메모리
1001375vjudge1은행 (IZhO14_bank)C++17
100 / 100
124 ms5548 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...