Submission #1141302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141302		Bilal_Coder	Bank (IZhO14_bank)	C++20	19 / 100	82 ms	4424 KiB

bank

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n, m; // Количество людей и купюр
vector<int> salaries, banknotes;
vector<int> sum; // Префиксная сумма зарплат
int dp[1 << 20]; // DP массив для масок (2^M максимум)

bool can(int mask, int s, int i) {
    if (s == sum[i]) { // Если текущая зарплата выплачена
        ++i;
        s = 0; // Переходим к следующему человеку
    }
    if (i == n) return true; // Все зарплаты выплачены

    int &res = dp[mask];
    if (res != -1) return res; // Если уже вычислено, возвращаем

    res = 0; // Изначально переход невозможен
    for (int j = 0; j < m; ++j) {
        if (!(mask & (1 << j)) && s + banknotes[j] <= sum[i]) { 
            // Если купюра ещё не использована и не превышает оставшуюся сумму
            if (can(mask | (1 << j), s + banknotes[j], i)) {
                res = 1; // Если нашли подходящий переход
                break;
            }
        }
    }
    return res;
}

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

    salaries.resize(n);
    banknotes.resize(m);
    sum.resize(n);

    for (int i = 0; i < n; ++i) cin >> salaries[i];
    for (int i = 0; i < m; ++i) cin >> banknotes[i];

    // Префиксная сумма зарплат
    sum[0] = salaries[0];
    for (int i = 1; i < n; ++i) {
        sum[i] = sum[i - 1] + salaries[i];
    }

    memset(dp, -1, sizeof(dp)); // Инициализируем dp массив как невычисленный

    // Запуск рекурсии
    if (can(0, 0, 0)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

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