Submission #1263882

#TimeUsernameProblemLanguageResultExecution timeMemory
1263882minhphanBank (IZhO14_bank)C++17
0 / 100
1 ms328 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; 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[dp.size() - 1] == N) { write_char('Y'); write_char('E'); write_char('S'); return 0; } } 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...