#include <bits/stdc++.h>
using namespace std;
constexpr int BUF_SZ = 1 << 15;
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
FILE *fin;
char next_char() {
if (pos == len) {
pos = 0;
len = (int) fread(buf, 1, BUF_SZ, fin);
if (!len) { return EOF; }
}
return buf[pos++];
}
int read_int() {
int x;
char ch;
int sgn = 1;
while (!isdigit(ch = next_char())) {
if (ch == '-') { sgn *= -1; }
}
x = ch - '0';
while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
return x * sgn;
}
// initialize input from file
void init_input() {
fin = fopen("bank.in", "r");
assert(fin != nullptr);
}
}
inline namespace Output {
char buf[BUF_SZ];
int pos;
FILE *fout;
void flush_out() {
fwrite(buf, 1, pos, fout);
pos = 0;
}
void write_char(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++] = (char) ('0' + (x % 10)); }
write_char((char) ('0' + x));
while (len) { write_char(num_buf[--len]); }
write_char('\n');
}
void init_output() {
fout = fopen("bank.out", "w");
assert(fout != nullptr);
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_input();
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[dp.size() - 1] == N) {
write_char('Y');
write_char('E');
write_char('S');
} else {
write_char('N');
write_char('O');
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |