Submission #1189711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189711		luffy15	Bank (IZhO14_bank)	C++20	19 / 100	1095 ms	868 KiB

bank

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

// Function to check if it's possible to pay exact salaries using available banknotes
bool canPaySalaries(vector< int > &salaries, vector< int > &banknotes, int person, vector< bool > &used) {
    if ( person == salaries.size( ) )
        return true; // All salaries paid

    int salary = salaries[person];

    // Try each banknote combination that sums to the current salary
    for ( int i = 0 ; i < banknotes.size( ) ; i++ ) {
        if ( !used[i] && banknotes[i] <= salary ) {
            if ( banknotes[i] == salary ) {
                used[i] = true;
                if ( canPaySalaries( salaries , banknotes , person + 1 , used ) )
                    return true;
                used[i] = false;
            } else {
                // Try to combine with other banknotes
                used[i] = true;
                if ( canPaySalaries( salaries , banknotes , person , used ) )
                    return true;
                used[i] = false;
            }
        }
    }

    return false;
}

int main() {
    int N, M;
    cin >> N >> M;

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

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

    // If sum of banknotes is less than sum of salaries, it's impossible
    long long sum_salaries = 0, sum_banknotes = 0;
    for ( int s: salaries )
        sum_salaries += s;
    for ( int b: banknotes )
        sum_banknotes += b;

    if ( sum_banknotes < sum_salaries ) {
        cout << "NO" << endl;
        return 0;
    }

    // For N=1 case (Subtask 1), check if any combination of banknotes sums to salary
    if ( N == 1 ) {
        int target = salaries[0];
        vector< bool > dp( target + 1 , false );
        dp[0] = true;

        for ( int b: banknotes ) {
            for ( int j = target ; j >= b ; j-- ) {
                dp[j] = dp[j] | dp[j - b];
            }
        }

        cout << (dp[target] ? "YES" : "NO") << endl;
        return 0;
    }

    // For general case, use backtracking
    vector< bool > used( M , false );
    cout << (canPaySalaries( salaries , banknotes , 0 , used ) ? "YES" : "NO") << endl;

    return 0;
}

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