Submission #475706

#	Time	Username	Problem	Language	Result	Execution time	Memory
475706		mat_v	Bank (IZhO14_bank)	C++14	19 / 100	474 ms	180932 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;

int a[25];
int b[25];

int pref[(1<<20)+5][21];
int ost[(1<<20)+5][21];
int sum[(1<<20)+5][21];
int niz[(1<<20)+5];
int kol[(1<<20)+5];

int popc(int x){
    int br = 0;
    ff(j,0,m - 1){
        if((1<<j)&x)br++;
    }
    return br;
}

bool cmp(int a, int b){
    return kol[a] < kol[b];
}

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    ff(i,0,n - 1)cin >> a[i];
    ff(i,0,m - 1)cin >> b[i];
    ff(i,0,(1<<m)-1){
        niz[i] = i;
        ff(j,0,m - 1)if((1<<j)&i)kol[i]++;
    }

    sort(niz, niz + (1<<m), cmp);

    ff(i,0,(1<<m)-1){
        int tr = niz[i];
        if(tr == 0){
            ff(j,0,n - 1)pref[tr][j] = j;
        }
        ff(j,0,n - 1){
            pref[tr][j] = j;
            ost[tr][j] = tr;
            int sm = 0;
            ff(k,0,m - 1){
                if(!((1<<k)&tr))continue;
                sm += b[k];
                int tmp = tr^(1<<k);
                int dkl = pref[tmp][j];
                if(dkl == n)pref[tr][j] = n;
                if(!ost[tmp][j])continue;
                if(pref[tr^ost[tmp][j]][dkl] > pref[tr][j]){
                    pref[tr][j] = pref[tr^ost[tmp][j]][dkl];
                    ost[tr][j] = pref[tr^ost[tmp][j]][dkl];
                }
            }
            if(sm == a[j]){
                if(j+1>pref[tr][j]){
                    pref[tr][j] = j+1;
                    ost[tr][j] = 0;
                }
            }
        }
    }
    if(pref[(1<<m)-1][0] >= n)cout << "YES\n";
    else cout << "NO\n";

    return 0;
}
/*
1 20
5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
*/

Compilation message (stderr)

bank.cpp: In function 'int popc(int)':
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:36:5: note: in expansion of macro 'ff'
   36 |     ff(j,0,m - 1){
      |     ^~
bank.cpp: In function 'int main()':
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:52:5: note: in expansion of macro 'ff'
   52 |     ff(i,0,n - 1)cin >> a[i];
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:53:5: note: in expansion of macro 'ff'
   53 |     ff(i,0,m - 1)cin >> b[i];
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:54:5: note: in expansion of macro 'ff'
   54 |     ff(i,0,(1<<m)-1){
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:56:9: note: in expansion of macro 'ff'
   56 |         ff(j,0,m - 1)if((1<<j)&i)kol[i]++;
      |         ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:61:5: note: in expansion of macro 'ff'
   61 |     ff(i,0,(1<<m)-1){
      |     ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:64:13: note: in expansion of macro 'ff'
   64 |             ff(j,0,n - 1)pref[tr][j] = j;
      |             ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:66:9: note: in expansion of macro 'ff'
   66 |         ff(j,0,n - 1){
      |         ^~
bank.cpp:6:27: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
bank.cpp:70:13: note: in expansion of macro 'ff'
   70 |             ff(k,0,m - 1){
      |             ^~

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