Submission #1225555

#TimeUsernameProblemLanguageResultExecution timeMemory
1225555minhpkKitchen (BOI19_kitchen)C++20
100 / 100
15 ms1096 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int a,b,c; int z[1000005]; int x[1000005]; int suma=0; int f[4000005]; int bruh=-1e16; int sumb=0; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b >> c; for (int i=1;i<=a;i++){ cin >> z[i]; suma+=z[i]; } for (int i=1;i<=b;i++){ cin >> x[i]; sumb+=x[i]; } for (int i=1;i<=a;i++){ if (z[i]<c){ cout << "Impossible" << "\n"; return 0; } } for (int i=1;i<=max(suma,sumb);i++){ f[i]=bruh; } for (int j=1;j<=b;j++){ for (int i=max(suma,sumb);i>=x[j];i--){ f[i]=max(f[i],f[i-x[j]]+min(x[j],a)); } } for (int i=1;i<=max(suma,sumb);i++){ if (f[i]>=a*c && i>=suma){ cout << i-suma << "\n"; return 0; } } cout << "Impossible" << "\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...