# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
938640 | 2024-03-05T11:36:01 Z | vjudge1 | Kitchen (BOI19_kitchen) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define int long long using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,k; cin >> n >> m >> k; vector<int> a(n),b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; int sum = 0LL; for (int i = 0; i < m; i++) sum+=b[i]; vector<vector<bool>> dp(m,vector<bool>(sum+1)); dp[0][0] = 1; dp[0][b[0]] = 1; for (int i = 1; i < m; i++) for (int j = b[i]; j <= sum; j++) dp[i][j] = (dp[i-1][j-b[i]] | dp[i-1][j]); int oth = 0; for (int i = 0; i < n; i++) oth+=a[i]; for (int i = oth; i <= sum; i++) if (dp[n-1][i]) { cout << i << '\n'; return; } return 0; }