Submission #1248788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248788		hamase	Bank (IZhO14_bank)	C++20	25 / 100	1093 ms	328 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll, ll>
#define mp make_pair
#define fi first
#define se second

ll N, M, a[200100], b[200100];
vector<pll> ca;

ll bs(ll x) {
    ll l = 0;
    ll r = (ll)ca.size()-1;
    ll mid;
    while (l <= r) {
        mid = (l + r)/2;
        if (ca[mid].fi > x) l = mid+1;
        else if (ca[mid].fi < x) r = mid-1;
        else return mid;
    }
    return -1;
}

bool ada(ll x) {
    ll in = bs(x);
    if (in != -1 && ca[in].se > 0) {
        ca[in].se--;
        return true;
    }
    for (int i = 0; i < ca.size(); i++) {
        if (ca[i].se < 1 || ca[i].fi > x) continue;
        ca[i].se--;
        if (ada(x-ca[i].fi)) {
            return true;
        } else ca[i].se++;
    }
    return false;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < M; i++) cin >> b[i];
    sort(a, a+N);
    sort(b, b+M, greater<ll>());

    ll cnt = 0;
    for (int i = 0; i < M; i++) {
        cnt++;
        if (i == N-1 || b[i] != b[i+1]) {
            ca.push_back(mp(b[i], cnt));
            cnt = 0;
        }
    }
    // for (pll a : ca) {
    //     cout << "(" << a.fi << ", " << a.se << ")" << endl;
    // }
    bool bisa = true;
    for (int i = 0; i < N; i++) {
        bool ae = ada(a[i]);
        // cout << a[i] << " " << (ae ? "yes" : "no") << endl;
        bisa &= ae;
    }
    cout << (bisa ? "YES" : "NO") << endl;
}

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