Submission #1105769

#TimeUsernameProblemLanguageResultExecution timeMemory
1105769vjudge1Kitchen (BOI19_kitchen)C++17
0 / 100
62 ms2884 KiB
#include <bits/stdc++.h> int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, k; std::cin >> n >> m >> k; std::vector<int> a(n), b(m); for (int i = 0; i < n; i++) { std::cin >> a[i]; } for (int i = 0; i < m; i++) { std::cin >> b[i]; } int64_t sumb = 0; for (int i = 0; i < m; i++) { sumb += b[i]; } if (k == 1) { int64_t suma = 0; for (int i = 0; i < n; i++) { suma += a[i]; } std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(sumb + 1, false)); dp[0][0] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j <= sumb; j++) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); if (j >= b[i - 1]) { dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i - 1]]); } } } for (int j = suma; j <= sumb; j++) { if (dp[n][j] == 1) { std::cout << j - suma << "\n"; return 0; } } std::cout << "Impossible\n"; return 0; } assert(false); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...