제출 #1000856

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000856		lucascgar	은행 (IZhO14_bank)	C++17	100 / 100	83 ms	8892 KiB

bank

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
https://oj.uz/problem/view/IZhO14_bank

ind[bmsk] last index of salaries formed with bmsk coins (answer would have ind[x] = n)
sum[bmsk] sum of bitmask after forming last salary


only maximize index, rest is always dependant on that
*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 20+1, MAXB = (1<<20), MAXV = 1e3+1;

int in[MAXB], sb[MAXB];  // in[bm]=first index you cant complete; sb[bm] = sobra

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;

    vector<int> p(n), b(m);
    for (auto &x:p) cin >> x;
    for (auto &x:b) cin >> x;

    int mb = (1<<m);
    bool ans = 0;
    for (int bm=1;bm<mb;bm++){
        in[bm] = 0, sb[bm] = 0;

        for (int i=0,a=1;i<m;i++, a<<=1) if ((a&bm)){

            if (in[bm^a] >= in[bm]){
                in[bm] = in[bm^a];
                sb[bm] = sb[bm^a] + b[i];

                if (sb[bm] == p[in[bm]]) in[bm]++, sb[bm] = 0;

            }
        
        }

        if (in[bm] == n){
            ans = 1;
            break;
        }
    }

    if (ans) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

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