Submission #1263883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263883		minhphan	Bank (IZhO14_bank)	C++17	100 / 100	92 ms	8520 KiB

bank

#include <bits/stdc++.h>

using namespace std;

constexpr int BUF_SZ = 1 << 15;

inline namespace Input {
    char buf[BUF_SZ];
    int pos;
    int len;

    char next_char() {
        if (pos == len) {
            pos = 0;
            len = static_cast<int>(fread(buf, 1, BUF_SZ, stdin));
            if (!len) { return EOF; }
        }
        return buf[pos++];
    }

    string read_line() {
        string result;
        while (true) {
            const char ch = next_char();
            if (ch == EOF) break;       // End of file
            if (ch == '\n') break;      // End of line
            result += ch;
        }
        return result;
    }

    int read_int() {
        char ch;
        int sgn = 1;
        while (!isdigit(ch = next_char())) {
            if (ch == '-') { sgn *= -1; }
        }
        int x = ch - '0';
        while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
        return x * sgn;
    }
}

inline namespace Output {
    char buf[BUF_SZ];
    int pos;

    void flush_out() {
        fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

    void write_char(const char c) {
        if (pos == BUF_SZ) { flush_out(); }
        buf[pos++] = c;
    }

    void write_int(int x) {
        static char num_buf[100];
        if (x < 0) {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10) { num_buf[len++] = static_cast<char>('0' + (x % 10)); }
        write_char(static_cast<char>('0' + x));
        while (len) { write_char(num_buf[--len]); }
        write_char('\n');
    }

    // auto-flush output when the program exits
    void init_output() { assert(atexit(flush_out) == 0); }
}

//naive Idee: Alle Permutationen testen und schauen, ob ich mit den ersten Banknoten die erste Person abbezahlen kann, usw. => O(n!*n)
int main() { //N=1 Rucksackproblem
    init_output();

    int N = read_int();
    int M = read_int();

    vector<int> people(N);

    for (int i = 0; i<N; i++) {
        people[i] = read_int();
    }

    vector<int> banknotes(M);

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

    /*std::sort(people.begin(), people.end(), std::greater<>());
    std::sort(banknotes.begin(), banknotes.end(), std::greater<>());*/

    //dp: Die maximale Anzahl, wie viele Personen von 0..i mit Banknoten in S abbezahlt werden können
    vector dp(1 << M, -1);

    //dp2: Das übriggebliebene Geld, nachdem wir die Personen mit Banknoten in S abbezahlt haben
    vector dp2(1 << M, -1);
    dp[0] = 0;
    dp2[0] = 0;

    for (int bitmask = 0; bitmask<dp.size(); bitmask++) {
        for (int m = 0; m<M; m++) {
            if ((bitmask & 1 << m) == 0) continue;
            int prev = bitmask ^ (1 << m);
            if (dp[prev] == -1) continue;

            int leftOver = dp2[prev] + banknotes[m];
            int person = people[dp[prev]];

            if (leftOver < person) {//Wenn die Person nicht abbezahlt werden kann, wird das übriggebliebene Geld erhöht
                dp[bitmask] = dp[prev];
                dp2[bitmask] = leftOver;
            } else if (leftOver == person) {//Wenn die Person komplett abbezahlt werden kann
                dp[bitmask] = dp[prev] + 1;
                dp2[bitmask] = 0;
            }
        }
        if (dp[bitmask] == N) {
            write_char('Y');
            write_char('E');
            write_char('S');
            return 0;
        }
    }
    write_char('N');
    write_char('O');
    return 0;
}

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