Submission #1112277

#TimeUsernameProblemLanguageResultExecution timeMemory
1112277kzhiBank (IZhO14_bank)C++14
100 / 100
338 ms92752 KiB
/*
    Author : kmv a.k.a kzhi
    K41 IT CHV
*/
#include <bits/stdc++.h>
using namespace std;


//#define int long long
#define ll long long
#define FOR(i,a,b) for (int i = a ; i <= b; ++ i)
#define FOD(i,a,b) for (int i = a; i >= b; -- i)


#define BIT(mask,i)       ((mask >> i) & 1)
#define MASK(i)                (1ll << (i))
#define OFFBIT(mask,i)  (mask &~(1ll<<(i)))
#define ONBIT(mask,i) (mask | (1ll << (i)))
#define lg2(x)    (63 - __builtin_clzll(x))
#define c_bit          __builtin_popcountll

#define vi vector < int >
#define all(a) a.begin(), a.end()
#define pb push_back

#define ii pair<int,int>
#define fi first
#define se second

#define openfile(TASK) if (fopen(TASK".inp","r"))\
        {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define endl '\n'
#define Faster ios_base::sync_with_stdio(false); \
                        cin.tie(0);  cout.tie(0);

#define mid(l,r) ((l + r) >> 1)
#define left(id) (id << 1)
#define right(id) ((id << 1) | 1)
#define ci const int

template <class X, class Y> bool maximize(X &a, const Y &b){if(a < b) return a = b, true;return false;}
template <class X, class Y> bool minimize(X &a, const Y &b){if(a > b) return a = b, true;return false;}

const int N = 1e3 + 5;
const int M = 21;

int n, m, a[M], b[M];
vi c[N];
int dp[M][MASK(20)];

void ql(int i, int sum, int mask){
    if (sum > 1000)
        return;
    if (i == m + 1){
        c[sum].pb(mask);
        return;
    }

    ql(i + 1, sum, mask);
    ql(i + 1, sum + b[i], ONBIT(mask, i - 1));
}

int sol(int i, int mask){
    if (i == n + 1)
        return 1;
    if (~dp[i][mask])
        return dp[i][mask];

    int cur = 0;

    for (int j : c[a[i]])
        if ((j & mask) == j)
            maximize(cur, sol(i + 1, mask ^ j));

    return dp[i][mask] = cur;
}

void SOLVE(){
    cin >> n >> m;
    FOR (i, 1, n)
        cin >> a[i];

    FOR (j, 1, m)
        cin >> b[j];

    ql(1, 0, 0);

    memset(dp, -1, sizeof(dp));

    int ok = sol(1, MASK(m) - 1);

    if (ok)
        cout << "YES";
    else
        cout << "NO";
}

signed main(){
    Faster
    openfile("bank")

    int q = 1;

//    cin >> q;

    while (q --){
        SOLVE();
    }

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:31:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bank.cpp:100:5: note: in expansion of macro 'openfile'
  100 |     openfile("bank")
      |     ^~~~~~~~
bank.cpp:31:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:100:5: note: in expansion of macro 'openfile'
  100 |     openfile("bank")
      |     ^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...