제출 #1089237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089237		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	16 ms	600 KiB

bank

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

// Глобальные переменные для удобства
int N, M;
vector<long long> salaries;
vector<long long> banknotes;
vector<bool> used_banknotes;

// Функция для рекурсивного поиска возможности выплатить зарплаты
bool backtrack(int employee_idx) {
    // Если все сотрудники обработаны, возвращаем true
    if (employee_idx == N) {
        return true;
    }

    long long current_salary = salaries[employee_idx];
    // Если текущая зарплата равна 0, переходим к следующему сотруднику
    if (current_salary == 0) {
        return backtrack(employee_idx + 1);
    }

    // Рекурсивная функция для поиска подмножества купюр, суммирующихся в current_salary
    // start — начальный индекс для перебора купюр
    // total — текущая сумма
    // prev — предыдущая купюра, чтобы избежать дубликатов
    function<bool(int, long long, long long)> dfs = [&](int start, long long total, long long prev) -> bool {
        if (total == current_salary) {
            // Если зарплата выплачена, переходим к следующему сотруднику
            return backtrack(employee_idx + 1);
        }
        if (total > current_salary) {
            return false;
        }
        for (int i = start; i < M; ++i) {
            if (!used_banknotes[i] && total + banknotes[i] <= current_salary) {
                // Пропускаем одинаковые купюры для оптимизации
                if (i > start && banknotes[i] == banknotes[i - 1] && !used_banknotes[i - 1]) {
                    continue;
                }
                used_banknotes[i] = true;
                if (dfs(i + 1, total + banknotes[i], banknotes[i])) {
                    return true;
                }
                used_banknotes[i] = false;
            }
        }
        return false;
    };

    return dfs(0, 0, -1);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    // Чтение входных данных
    cin >> N >> M;
    salaries.resize(N);
    for(int i = 0; i < N; ++i){
        cin >> salaries[i];
    }
    banknotes.resize(M);
    for(int i = 0; i < M; ++i){
        cin >> banknotes[i];
    }

    // Сортируем зарплаты и купюры в порядке убывания
    sort(salaries.begin(), salaries.end(), greater<long long>());
    sort(banknotes.begin(), banknotes.end(), greater<long long>());

    // Проверка, что сумма зарплат не превышает сумму купюр
    long long total_salary = 0;
    for(auto a : salaries) total_salary += a;
    long long total_banknotes = 0;
    for(auto b : banknotes) total_banknotes += b;
    if(total_salary > total_banknotes){
        cout << "NO";
        return 0;
    }

    used_banknotes.assign(M, false);

    // Запуск backtracking
    if(backtrack(0)){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}

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