Submission #640609

#	Time	Username	Problem	Language	Result	Execution time	Memory
640609		gnhmhp	Bank (IZhO14_bank)	C++14	71 / 100	1070 ms	109068 KiB

bank

#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";
}

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