제출 #1098232

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

bank

// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ins insert
#define F first
#define S second
#define fx cout << fixed << setprecision(6);
#define md (tl+tr)/2
#define TL v+v, tl,md
#define TR v+v+1, md+1,tr
#define Tl t[v].l, tl,md
#define Tr t[v].r, md+1,tr
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define all(x) (x).begin(), (x).end()
#define int ll
#define cnk(n,k) mod(mod(f[(n)]*binpow(f[(n)-(k)],M-2))*binpow(f[(k)],M-2))
#define cnkf(n,k) mod(mod(f[(n)]*inv[(n)-(k)])*inv[(k)])

using namespace std;

typedef complex<double> cd;

struct mine{int l;int r;int i;};
struct edge{int u;int v;int w;};
struct tree{int l;int r;int val;};

auto cmp = [](mine a, mine b) { return a.i<b.i; };

mt19937 RR((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
 
int random(int l, int r){
  return uniform_int_distribution<int>(l, r)(RR);
}

int M=998244353;

int mod1(int a,int b=M) {
    if (a<0)
        a=b+a%b;
    return a % b;
}

int binpow(int a,int n,int m=M) {
    a=mod1(a,m);
    if (!n)
        return 1;
    if (n&1)
        return (a * binpow(a,n-1))%m;
    int x = binpow(a,n>>1);
    return (x*x)%m; 
}

const ll INF=1e18+7;
const int N=2e6+7;

int n,m,a[N],b[N],sum[N],f,L,R;
vector <int> s[101];
bool u[101][N],u1[101][N];

void rec1(int x,int y=0,int i=0) {
    if (i>=m) {
        if (u[R][y] and !u[f][x+y]) {
            s[f].pb(x+y);
            u[f][x+y]=true;
        }
        return;
    }
    rec1(x,y,i+1);
    if (!(x>>i&1))
        rec1(x,y+(1<<i),i+1);
}

void rec(int v,int l,int r) {
    if (l==r) {
        for (int i=0;i<(1<<m);i++) {
            if (sum[i]==a[l]) {
                u[v][i]=true;
                s[v].pb(i);
            }
        }
        if (s[v].empty()) {
            no;
            exit(0);
        }
        return;
    }
    int mid=random(l,r);
    rec(v+v,l,mid), rec(v+v+1,mid+1,r);
    L=v+v,R=v+v+1;
    if (s[L].size()>s[R].size())
        swap(L,R);
    // cout << v << endl;
    for (auto now : s[L]) {
        f=v;
        rec1(now);
    }
    if (s[v].empty()) {
        no;
        exit(0);
    }
}

void solve() {
    cin >> n >> m;
    for (int i=1;i<=n;i++)
        cin >> a[i];
    for (int i=1;i<=m;i++)
        cin >> b[i];
    for (int i=0;i<(1<<m);i++) {
        sum[i]=0;
        for (int j=0;j<m;j++) {
            if (i>>j&1) {
                sum[i]=sum[i^(1<<j)]+b[j+1];
                break;
            }
        }
    }
    rec(1,1,n);
    yes;
}   

signed main() {
    /*
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    */
    // fx
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
            count++;
        }
    }
    return 0;
}

// ctrl + shift + p make stress isis__Good isis__Generator

// g++ -std=c++17 (path) -o run
// .\run

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