# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
746010 | 2023-05-21T10:33:38 Z | vjudge1 | Kitchen (BOI19_kitchen) | C++17 | 282 ms | 108332 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 301; const int MAXS = MAXN*MAXN+1000; int dp[MAXN][MAXS], n, m, k; void solve() { vector<int> a(n+1), b(n+1); for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int j = 1; j <= m; j++) { cin >> b[j]; } int ans = INT_MAX; for (int bits = 0; bits < (1 << m); bits++) { int x = bits<<1; priority_queue<int> pq; for (int i = 1; i <= n; i++) { pq.push(a[i]); } multiset<int> chefs; for (int i = 1; i <= m; i++) { if ((x>>i)&1) { chefs.insert(b[i]); } } bool possible = true; while (!pq.empty() && !chefs.empty()) { bool good = false; int left = pq.top(); pq.pop(); if (chefs.size() < k || left < k) { possible = false; break; } while (left && !chefs.empty()) { vector<int> used; for (int u : chefs) { if (left) { left--; used.push_back(u); } } for (int u : used) { chefs.erase(chefs.find(u)); if (u != 1) chefs.insert(u-1); } } if (left) { possible = false; break; } } if (possible && pq.empty()) { int res = 0; for (int u : chefs) res += u; ans = min(ans, res); } } if (ans == INT_MAX) cout << "Impossible\n"; else cout << ans << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; if (k != 1) { solve(); return 0; } vector<int> a(n+1), b(m+1); int sum = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } for (int j = 1; j <= m; j++) { cin >> b[j]; } dp[0][0] = true; for (int i = 1; i <= m; i++) { for (int j = 0; j < MAXS; j++) { dp[i][j] = dp[i-1][j]; } for (int j = b[i]; j < MAXS; j++) { if (dp[i-1][j-b[i]]) { dp[i][j] = true; } } } for (int i = 0; i < MAXS; i++) { if (dp[m][i]) cerr << i << " "; } for (int i = sum; i < MAXS; i++) { if (dp[m][i]) { cout << i-sum << "\n"; return 0; } } cout << "Impossible\n"; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 2 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 228 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 2 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 228 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Runtime error | 2 ms | 468 KB | Execution killed with signal 6 |
10 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 132 ms | 93996 KB | Output is correct |
2 | Correct | 135 ms | 81452 KB | Output is correct |
3 | Correct | 190 ms | 108124 KB | Output is correct |
4 | Correct | 257 ms | 108332 KB | Output is correct |
5 | Correct | 282 ms | 104652 KB | Output is correct |
6 | Correct | 102 ms | 74996 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 468 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 980 KB | Output is correct |
2 | Correct | 2 ms | 980 KB | Output is correct |
3 | Correct | 1 ms | 980 KB | Output is correct |
4 | Correct | 1 ms | 228 KB | Output is correct |
5 | Correct | 1 ms | 968 KB | Output is correct |
6 | Correct | 1 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 980 KB | Output is correct |
9 | Runtime error | 2 ms | 468 KB | Execution killed with signal 6 |
10 | Halted | 0 ms | 0 KB | - |