Submission #439813

#	Time	Username	Problem	Language	Result	Execution time	Memory
439813		training4usaco	Bank (IZhO14_bank)	C++11	100 / 100	132 ms	8524 KiB

bank

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

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

    vector<int> targets(n);
    vector<int> banknotes(m);

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

    // vector<vector<int>> possiblem(n);   // possible masks of banknotes for each target

    // for(int i = 0; i < n; ++i) {
    //     for(int s = 1; s < (1 << m); ++s) {
    //         int money = 0;
    //         for(int j = 0; j < m; ++j) {
    //             if(s & (1 << j)) {
    //                 money += banknotes[j];
    //             }
    //         }

    //         if(money == targets[i]) {
    //             possiblem[i].push_back(s);
    //         }
    //     }
    // }

    vector<int> num_paid((1 << m), -1);       // number of people covered
    vector<int> unused((1 << m), -1);     // amount of money unused

    num_paid[0] = 0;
    unused[0] = 0;

    bool answered = false;

    for(int mask = 0; mask < (1 << m); ++mask) {
        for(int next = 0; next < m; ++next) {
            if((mask & (1 << next)) == 0) {
                // cout << "next: " << next << endl;
                // cout << mask << ": broke" << endl;
                continue;
            }
            // cout << mask << ": didn't break" << endl;
            int prevm = (mask ^ (1 << next));
            // cout << "prevm: " << prevm << endl;
            if(num_paid[prevm] != -1) {
                // cout << "prevm isn't -1" << endl;
                int money = unused[prevm] + banknotes[next];

                if(money < targets[num_paid[prevm]]) {
                    num_paid[mask] = num_paid[prevm];
                    unused[mask] = money;
                }
                else if(money == targets[num_paid[prevm]]) {
                    num_paid[mask] = num_paid[prevm] + 1;
                    unused[mask] = 0;
                }
                else if(unused[prevm] == targets[num_paid[prevm]]) {
                    num_paid[mask] = num_paid[prevm] + 1;
                    unused[mask] = banknotes[next];
                }
            }
        }
        if(num_paid[mask] == n) {
            cout << "YES" << endl;
            answered = true;
            break;
        }
    }

    for(int i = 0; i < (1 << m); ++i) {
        // cout << i << ": " << num_paid[i] << " " << unused[i] << endl;
    }

    if(!answered) {
        cout << "NO" << endl;
    }

}

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