Submission #1068981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068981		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	532 ms	50856 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define lli long long int
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define vl vector<ll>
#define pstr pair<string, string>
#define sz size()
#define pb push_back
#define pf push_front
#define ff first
#define ss second
#define mk make_pair
const ld pi = 3.14159265358979323846;
const ll MOD = 1e9 + 7;
const ll N = 1e6 + 5;
const int maxn = 1e3 + 10;
const ll inf = 1e18;
ll bpm(ll x,ll y,ll m){if(y==0)return 1%m;if(y==1)return x%m;ll p=bpm(x,y/2,m);if(y%2==0)return p*p%m;else return p*p%m*x%m;}
ll bp(ll x,ll y){if(y==0)return 1;if(y==1)return x;ll p=bp(x,y/2);if(y%2==0)return p*p;else return p*p*x;}
ll lcm(ll a, ll b){return (a / __gcd(a, b)) * b;}
bool isPrime(ll n){for(ll i=2; i<=sqrt(n); i++){ if(n%i==0){return false;}}return true;}
bool cmp(const pair<ll,ll>& a, const pair<ll, ll>& b){return a.ss > b.ss;}

ll n, m, a[maxn], b[maxn];
vl v[maxn];
unordered_map<ll, bool> mp[21];

void f(ll i, ll x){
    if(mp[i][x]) return;
    mp[i][x] = 1;
    if(i == n){
        cout << "YES\n";
        exit(0);
    }
    for(ll y : v[a[i]]){
        if((x & y) == 0){
            f(i + 1, x + y);
        }
    }
}

void solve(/*＜(´= w =`)＞*/){
    cin >> n >> m;
    for(ll i = 0; i < n; i++) cin >> a[i];
    for(ll i = 0; i < m; i++) cin >> b[i];
    for(ll x = 0; x < (1 << m); x++){
        ll sum = 0;
        for(ll i = 0; i < m; i++){
            if((1 << i) & x) sum += b[i];
        }
        if(sum <= 1e3) v[sum].pb(x);
    }
    f(0, 0);
    cout << "NO\n";
    return;
}

int main(/*d1ZzAster1*/)
{
    boost
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    // setlocale(LC_ALL, "RU");
    ll T = 1;
    // cin >> T;
    for(ll tt = 1; tt <= T; tt++){
        solve();
    }
    return 0;
}

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