Submission #781952

#	Time	Username	Problem	Language	Result	Execution time	Memory
781952		nirmalg	Bank (IZhO14_bank)	C++14	100 / 100	99 ms	8532 KiB

bank

#include "bits/stdc++.h"
using namespace std;

// Template modified from https://usaco.guide/general/generic-code?lang=cpp#templates 

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;

#define Sum(v) (accumulate(v.begin(), v.end(), 0ll))
#define Sort(v) (sort(v.begin(), v.end()))


constexpr ll INF = 1e9;
constexpr int MOD = 998244353;

// #define IO(NAME) \
//     cin.tie(0)->sync_with_stdio(0); \
//     if(fopen(NAME ".in","r")) freopen(NAME ".in","r",stdin), \
//     freopen(NAME ".out","w",stdout);

template <typename T1, typename T2> // cin >> pair<T1, T2>
istream &operator>>(istream &istream, pair<T1, T2> &p)
{
    return (istream >> p.first >> p.second);
}
 
template <typename T> // cin >> vector<T>
istream &operator>>(istream &istream, vector<T> &v)
{
    for (auto &it : v)
        cin >> it;
    return istream;
}
 
template <typename T1, typename T2> // cout << pair<T1, T2>
ostream &operator<<(ostream &ostream, const pair<T1, T2> &p)
{
    return (ostream << p.first << " " << p.second);
}
template <typename T> // cout << vector<T>
ostream &operator<<(ostream &ostream, const vector<T> &c)
{
    for (auto &it : c)
        cout << it << " ";
    return ostream;
}


// bitwise ops
// j is 0 based indexing 
// __builtin_ctzll() for long long and __ builtin_popcount()
#define LSB(S) ((S) & -(S))


ll LCM(int a, int b)
{
    return ((ll)a * b) / __gcd(a, b);
}

bool nCr_Parity(int n, int r){
    int i = 0;
    while(i <= 30){ // for 32 bit integers
        int x = 1<<i;
        if((x&r) > (x&n)) return 0;
        ++i;
    }
    return 1; // 1 is odd 
}

bool solve(){
    int n, m;
    cin >> n >> m;
    vi a(n), b(m);
    cin >> a >> b;
    int hi = (1 << m);
    vpii dp(hi, {0, 0});
    for(int mask = 0; mask < hi; ++mask){
        if(dp[mask].first == n) return true;
        for(int i = 0; i < m; ++i){
            if((mask & (1 << i)) == 0){
                int newmask = mask ^ (1 << i);
                pii newstate;
                if(dp[mask].second + b[i] == a[dp[mask].first]){
                    newstate = {dp[mask].first + 1, 0};
                }
                else{
                    newstate = {dp[mask].first, dp[mask].second + b[i]};
                }
                dp[newmask] = max(dp[newmask], newstate);
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(10) << fixed;
    // IO(""); 

    puts(solve()? "YES" : "NO");
}
// when using printf, scanf for long long use %dll
// when using accumulate use 0ll if sum is long long 

Compilation message (stderr)

bank.cpp:27:1: warning: multi-line comment [-Wcomment]
   27 | // #define IO(NAME) \
      | ^

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