제출 #1164413

#제출 시각아이디문제언어결과실행 시간메모리
1164413ivaziva은행 (IZhO14_bank)C++17
100 / 100
98 ms8644 KiB
#include <bits/stdc++.h>

using namespace std;

#define MAXN 20

int n,m;
int a[MAXN],b[MAXN];
int dp[1<<MAXN],dp1[1<<MAXN];

int main()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=0;i<n;i++) cin>>a[i];
    for (int i=0;i<m;i++) cin>>b[i];
    dp[0]=dp1[0]=0;
    for (int maska=1;maska<(1<<m);maska++) {dp[maska]=-1;dp1[maska]=-1;}
    for (int maska=1;maska<(1<<m);maska++)
    {
        for (int bit=0;bit<m;bit++)
        {
            if ((maska&(1<<bit))==0) continue;
            if (dp[maska^(1<<bit)]==-1) continue;
            int target=a[dp[maska^(1<<bit)]],left=dp1[maska^(1<<bit)]+b[bit];
            if (left<target) {dp[maska]=dp[maska^(1<<bit)];dp1[maska]=left;}
            else if (left==target) {dp[maska]=dp[maska^(1<<bit)]+1;dp1[maska]=0;}
        }
        if (dp[maska]==n) {cout<<"YES"<<endl;return 0;}
    }
    cout<<"NO"<<endl;return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...