제출 #1324025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324025		sh_qaxxorov_571	은행 (IZhO14_bank)	C++20	100 / 100	84 ms	8612 KiB

bank

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Bank masalasi - Bitmask DP yechimi
 * Vaqt murakkabligi: O(M * 2^M)
 */

int main() {
    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    vector<int> b(M);
    for (int i = 0; i < M; i++) cin >> b[i];

    // dp[mask] - ushbu maska yordamida to'liq maosh olgan odamlar soni
    // rem[mask] - joriy (dp[mask]-inchi) odam uchun yig'ilgan banknotlar summasi
    vector<int> dp(1 << M, -1);
    vector<int> rem(1 << M, 0);

    dp[0] = 0;
    rem[0] = 0;

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

        // Agar barcha N kishi maoshini olgan bo'lsa
        if (dp[mask] == N) {
            cout << "YES" << endl;
            return 0;
        }

        for (int i = 0; i < M; i++) {
            // Agar i-chi banknot hali ishlatilmagan bo'lsa
            if (!(mask & (1 << i))) {
                int next_mask = mask | (1 << i);
                int current_person = dp[mask];
                int new_sum = rem[mask] + b[i];

                int next_dp = dp[mask];
                int next_rem = new_sum;

                // Agar banknotlar yig'indisi joriy odamning maoshiga teng bo'lsa
                if (new_sum == a[current_person]) {
                    next_dp++;
                    next_rem = 0;
                } 
                // Agar kichik bo'lsa, davom etamiz
                else if (new_sum > a[current_person]) {
                    // Bu banknot bilan maoshni to'lab bo'lmaydi
                    continue;
                }

                // DP holatini yangilash (ko'proq odamga to'lash yoki qoldiqni kamaytirish)
                if (next_dp > dp[next_mask] || (next_dp == dp[next_mask] && next_rem < rem[next_mask])) {
                    dp[next_mask] = next_dp;
                    rem[next_mask] = next_rem;
                }
            }
        }
    }

    // Oxirgi tekshiruv
    for(int mask = 0; mask < (1 << M); mask++) {
        if (dp[mask] == N) {
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;
    return 0;
}

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