제출 #640609

#제출 시각아이디문제언어결과실행 시간메모리
640609gnhmhp은행 (IZhO14_bank)C++14
71 / 100
1070 ms109068 KiB
#define taskname "bank."
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;

int n, m;
int a[20], b[20];
bool c1[1<<20], c2[1<<20];
vector<int> v[1<<20];
pair<int, int> p[1<<20];

void upd(int i)
{
    if (c1[i]) return;
    c1[i]=true;
    for (auto x : v[i]) upd(i|(1<<x));
}

int main()
{
    fastio;
    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=0; i<(1<<m); ++i)
    {
        int s=0;
        for (int j=0; j<m; ++j)
            if (i & (1<<j)) s+=b[j];
            else v[i].push_back(j);
        p[i].first=s; p[i].second=i;
    }
    sort(p, p+(1<<m));
    int j=0, sum=0;
    bool check=true;
    upd(0); swap(c1,c2);
    for (int i=0; i<n && check; ++i)
    {
        fill(c1, c1+(1<<m), 0);
        check=false; sum+=a[i];
        while (p[j].first<sum) ++j;
        while (p[j].first==sum)
        {
            if (c2[p[j].second])
                upd(p[j].second), check=true;
            ++j;
        }
        swap(c1,c2);
    }
    if (check) 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...