Submission #679570

#	Time	Username	Problem	Language	Result	Execution time	Memory
679570		shalekberli	Bank (IZhO14_bank)	C++17	100 / 100	508 ms	36240 KiB

bank

/*
BY: shalekberli (Shahin Alekberli)
LANG: C++
*/
  
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  
#include<bits/stdc++.h>
//MACROS//
#define need_for_speed ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define _crt_secure_no_warnings
#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define INF 0x3F3F3F3F
#define INFL 0x3F3F3F3F3F3F3F3FLL
#define UB upper_bound
#define LB lower_bound
#define F first
#define S second
#define mod 1000000007LL
#define MOD 998244353LL
#define MoD 16714589LL
#define moD 1000000LL;
#define Max 1e12
#define ll long long
#define lld long double
#define usi unsigned int
#define ull unsigned long long
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pcc pair<char, char>
#define fix(n, k) fixed << setprecision((k)) << (n)
#define loop1(i, n, d) for (ll i = 1; i <= (n); i += (d))
#define loop0(i, n, d) for (ll i = 0; i < (n); i += (d))
#define loop(i, k, n, d) for(ll i = (k);i <= (n);i += (d))
#define loopr(i, k, n, d) for (ll i = (k); i >= (n); i -= (d))
#define loopch(i, k, n, d) for(char i = (k); i <= (n);i += (d))
#define loopchr(i, k, n, d) for(char i = (k); i >= (n);i -= (d))
#define read(x) for(auto &i: x) cin >> i
#define readi(x) for(int &i : x) cin >> i
#define readll(x) for(ll &i : x) cin >> i
#define readp(x) for(auto &i : x) cin >> i.F >> i.S;
#define write(x) for(auto &i: x) cout << i << " "
#define writend(x) for(auto &i: x) cout << i << endl
#define writep(x) for(auto &i: x) cout << i.F << " " << i.S << endl
#define alphalower "abcdefghijklmnopqrstuvwxyz"
#define alphaupper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
using namespace std;

int n, m;
vector<int> a(25), b(25);
vector<int> masks[25000];

bool dp[25][(1 << 20) + 10];
bool used[25][(1 << 20) + 10];

bool f(int pos, int mask){
    if(pos == n) return true;
    if(used[pos][mask]) return dp[pos][mask];
    used[pos][mask] = true;
    bool res = false;
    for(auto to : masks[a[pos]]){
        if((mask & to) != 0) continue;
        res = (res | (f(pos + 1, (mask | to))));
    }
    return dp[pos][mask] = res;
}

void solve(){
    cin >> n >> m;
    loop0(i, n, 1) cin >> a[i];
    loop0(j, m, 1) cin >> b[j];
    loop0(i, (1 << m), 1){
        int cursum = 0;
        loop0(j, m, 1){
            if((i & (1 << j))){
                cursum += b[j];
            }
        }
        masks[cursum].pb(i);
    }
    loop0(i, n, 1){
        if(masks[a[i]].empty()){
            NO;
            return;
        }
    }
    if(f(0, 0)) YES;
    else NO;
}

void Tour_de_Force(string head_hunter){
    string head_hunter1 = head_hunter + ".in";
    freopen(head_hunter1.c_str() , "r", stdin);
    string head_hunter2 = head_hunter + ".out";
    freopen(head_hunter2.c_str() , "w", stdout);
}

int main(){
    need_for_speed
    //Tour_de_Force("lazy");
    solve();
    /* ll t; cin >> t;
    while(t--){
        solve();
    } */
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

bank.cpp: In function 'void Tour_de_Force(std::string)':
bank.cpp:104:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     freopen(head_hunter1.c_str() , "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:106:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |     freopen(head_hunter2.c_str() , "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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