Submission #1099284

#TimeUsernameProblemLanguageResultExecution timeMemory
1099284sitablechairKitchen (BOI19_kitchen)C++17
100 / 100
92 ms107616 KiB
#include <bits/stdc++.h> #define ll long long #define ldb long double #define endl '\n' #define For(i,l,r) for(int i=l;i<=r;i++) #define ForD(i,r,l) for(int i=r;i>=l;i--) #define REP(i,l,r) For(i,l,r-1) #define PER(i,r,l) ForD(i,r-1,l) #define ff first #define ss second #define pb push_back #define all(x) x.begin(),x.end() #define All(x,n) x+1,x+1+n #define Alll(x,n) x,x+n #define sz(x) (signed)x.size() #define unq(x) x.resize(unique(all(x))-x.begin()) #define mpa make_pair #ifdef NCGM #include"debug.h" #else #define debug(...) "fr"; #endif using namespace std; const int N=303; int n,m,k; int a[N],b[N],f[N][N*N]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> k; int tmp=0; For(i,1,n) { cin >> a[i]; tmp+=a[i]; } For(i,1,m) cin >> b[i]; For(i,1,n) if (a[i]<k) return !(cout << "Impossible"); For(i,0,n) For(j,0,max(m,n)*300) f[i][j]=-2e9; f[0][0]=0; For(i,1,m) For(j,0,max(m,n)*300) { f[i][j]=f[i-1][j]; if (j>=b[i]) f[i][j]=max(f[i][j],f[i-1][j-b[i]]+min(b[i],n)); } int ans=2e9; For(j,tmp,max(m,n)*300) if (f[m][j]>=n*k) ans=min(ans,j-tmp); if (ans>=2e9) cout << "Impossible"; else cout << ans; 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...