Submission #1186345

#TimeUsernameProblemLanguageResultExecution timeMemory
1186345kl0989eKitchen (BOI19_kitchen)C++20
100 / 100
83 ms99144 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]; for (int i=0; i<=m; i++) { for (int j=0; j<=s; j++) { dp[i][j]=-1e9; } } dp[0][0]=0; 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...