제출 #1186341

#제출 시각아이디문제언어결과실행 시간메모리
1186341kl0989eKitchen (BOI19_kitchen)C++20
21 / 100
52 ms67908 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back #define vi vector<int> #define vl vector<ll> #define pi pair<int, int> #define pl pair<ll,ll> #define all(x) (x).begin(),(x).end() int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m,k; cin >> n >> m >> k; vi a(n); vi b(m); for (int i=0; i<n; i++) { cin >> a[i]; } for (int i=0; i<m; i++) { cin >> b[i]; } int s=accumulate(all(b),0); int s2=accumulate(all(a),0); if (*min_element(all(a))<k || m<k || s<s2) { cout << "Impossible\n"; return 0; } int dp[m+1][s+1]; memset(dp,0,sizeof(dp)); for (int i=0; i<m; i++) { for (int j=0; j<=s; j++) { dp[i+1][j]=max(dp[i+1][j],dp[i][j]); if (j+b[i]<=s) { dp[i+1][j+b[i]]=max(dp[i+1][j+b[i]],dp[i][j]+min(n,b[i])); } } } int ans=1e9; for (int j=s2; j<=s; j++) { if (dp[m][j]>=n*k) { ans=min(ans,j-s2); } } if (ans==1e9) { cout << "Impossible\n"; } else { cout << ans << '\n'; } 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...