제출 #1326608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326608		mrcat2011	은행 (IZhO14_bank)	C++20	100 / 100	86 ms	16844 KiB

bank

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef string str;
typedef double dbl;
typedef char boolean;   

#define MOD 1000000000
#define println(n) cout << n << endl
#define print(n) cout << n << ' '
#define input(n) cin >> n;
#define vll vector<ll> 
#define vc vector<char>
#define vstr vector<str>
#define vdbl vector<dbl>
#define vbln vector<boolean>
#define vpll vector<pair<ll, ll>>
#define vplb vector<pair<ll, boolean>>  
#define vvl  vector<vector<ll>>
#define all(a) a.begin(), a.end()
#define mll map<ll, ll>
#define mcl map<char, ll>
#define mlb map<ll, boolean>
#define mcb map<char, bool>
#define mstrl map<str, ll>
#define mlstr map<ll, str>
#define sll set<ll> 
#define sc set<char>
#define sstr set<str>
#define sdbl set<dbl>
#define sbln set<boolean>
#define msll multiset<ll> 
#define msc multiset<char>
#define msstr multiset<str>
#define msdbl multiset<dbl>
#define msbln multiset<boolean>
#define pll pair<ll, ll>
#define hurryupmrcat ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

template<typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (T& x : v) is >> x;
    return is;
}

template<typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    for (T x : v) os << x << ' ';
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, set<T>& st) {
    for (T x : st) os << x << ' ';
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, multiset<T>& mst) {
    for (T x : mst) os << x << ' ';
    return os;
}

vll stov(str s) {
    vll v;
    for (char c : s) {
        v.emplace_back(c - '0');
    }
    return v;
}

const ll MAX = 2e5 + 5;

struct BIT {
    ll n;
    vll ft;
    BIT(ll N) {
        n = N + 10;
        ft.assign(n + 5, 0);
    }
    void add(ll idx, ll val) {
        for (; idx <= n; idx += (idx & (-idx))) {
            ft[idx] += val;
        }
    }
    ll get(ll idx) {
        ll ret = 0;
        for (; idx >= 0; idx -= (idx & (-idx))) {
            ret += ft[idx];
        }
        return ret;
    }
};

bool Comp(pll p1, pll p2) {
    if (p1.second < p2.second) return false;
    return true;
}

ll Max (ll a, ll b) {
    if (a >= b) return a;
    return b;
}

ll Min (ll a, ll b) {
    if (a >= b) return b;
    return a;
}

void solve () {
    ll n, m; 
    if(!(cin >> n >> m)) return;

    vll v1(n); cin >> v1;
    vll v2(m); cin >> v2;

    vll dp((1 << m), -1);
    vll dp2((1 << m), -1);

    dp[0] = 0;
    dp2[0] = 0;

    for (ll mask = 0; mask < (1 << m); ++mask) {
        if (dp[mask] == -1) continue;

        if (dp[mask] == n) {
            cout << "YES" << endl;
            return;
        }

        for (ll j = 0; j < m; ++j) {
            if (!(mask & (1 << j))) {
                ll nw = mask | (1 << j);
                
                if (dp[mask] < n) {
                    ll sum = dp2[mask] + v2[j];

                    if (sum < v1[dp[mask]]) {
                        dp[nw] = dp[mask];
                        dp2[nw] = sum;
                    } 
                    else if (sum == v1[dp[mask]]) {
                        dp[nw] = dp[mask] + 1;
                        dp2[nw] = 0;
                    }
                }
            }
        }
    }

    cout << "NO" << endl;
}

int main(int argc, char const *argv[]) {  
    hurryupmrcat
    ll t = 1;
    for (size_t cs = 1; cs <= t; ++cs) {
        solve();
    }
    return 0;
}

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