제출 #1323993

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

bank

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

using namespace std;

int N, M;
vector<int> salary;
vector<int> bills;
bool found = false;

// Backtracking funksiyasi
void solve(int person_idx) {
    if (found) return;
    
    // Agar barcha odamlarga maosh berib bo'lingan bo'lsa
    if (person_idx == N) {
        found = true;
        return;
    }

    // Joriy odam uchun banknotlar kombinatsiyasini qidirish
    // Bu qismda Subset Sum algoritmi yoki ichki backtracking ishlatiladi
}

/* Soddaroq yondashuv: Har bir banknotni biror odamga berishga urinib ko'rish.
   Har bir banknot ixtiyoriy bitta odamga tegishli bo'lishi yoki umuman ishlatilmasligi mumkin.
*/

bool can_pay(int bill_idx, vector<int>& current_salaries) {
    if (bill_idx == M) {
        for (int s : current_salaries) {
            if (s != 0) return false;
        }
        return true;
    }

    for (int i = 0; i < N; i++) {
        if (current_salaries[i] >= bills[bill_idx]) {
            current_salaries[i] -= bills[bill_idx];
            if (can_pay(bill_idx + 1, current_salaries)) return true;
            current_salaries[i] += bills[bill_idx]; // Backtrack
        }
    }
    
    // Banknotni ishlatmaslik holati
    if (can_pay(bill_idx + 1, current_salaries)) return true;

    return false;
}

int main() {
    cin >> N >> M;
    salary.resize(N);
    for (int i = 0; i < N; i++) cin >> salary[i];
    bills.resize(M);
    for (int i = 0; i < M; i++) cin >> bills[i];

    // Kattaroq banknotlarni oldinroq tekshirish samaraliroq
    sort(bills.rbegin(), bills.rend());

    if (can_pay(0, salary)) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

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