제출 #908789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908789		khachatur25	은행 (IZhO14_bank)	C++14	100 / 100	112 ms	8792 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> v(n);
    vector<int> vc(m);

    for (auto& elem : v) cin >> elem;
    for (auto& elem : vc) cin >> elem;

    vector<int> dzaxot(1 << m, -1);
    vector<int> mardik(1 << m, -1);

    dzaxot[0] = 0;
    mardik[0] = 0;

    for (int s = 0; s < (1 << m); s++) {
        for (int last = 0; last < m; last++) {
            if ((s & (1 << last)) == 0) continue;

            int prev = s & ~(1 << last);

            if (mardik[prev] == -1) continue;

            int tiv = dzaxot[prev] + vc[last];
            int cel = v[mardik[prev]];

            if (tiv < cel) {
                mardik[s] = mardik[prev];
                dzaxot[s] = tiv;
            } else if (tiv == cel) {
                mardik[s] = mardik[prev] + 1;
                dzaxot[s] = 0;
            }
        }

        if (mardik[s] == n) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
}

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