Submission #1263871

#TimeUsernameProblemLanguageResultExecution timeMemory
1263871minhphanBank (IZhO14_bank)C++17
0 / 100
0 ms320 KiB
#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_output(); init_input(); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...