Submission #514906

#TimeUsernameProblemLanguageResultExecution timeMemory
514906MahdiKitchen (BOI19_kitchen)C++17
100 / 100
14 ms972 KiB
#include<bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; #define all(v) v.begin(), v.end() #define F first #define S second typedef long long ll; typedef pair<int, int> pii; const int N=305; int n, m, k, a[N], b[N], c[N*N], d[N*N]; bitset<N*N>e; int s=1, ss=1; int bin(int l){ if(e[l]) return l; int r=ss, h=d[l]; while(r-l>1){ int mid=(l+r)/2; if(d[mid]>h) r=mid; else l=mid; } if(r==ss) return 2e9; return r; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>k; for(int i=0;i<n;++i) cin>>a[i]; for(int i=0;i<m;++i) cin>>b[i]; for(int i=0;i<n;++i){ if(a[i]<k){ cout<<"Impossible"; return 0; } } sort(b, b+m); int id=0; while(id<m && b[id]<n) ++id; for(int i=id;i<m;++i) s+=b[i]; memset(c, -1, sizeof(c)); c[0]=0; for(int i=id;i<m;++i){ for(int j=s-1;j>=b[i];--j){ if(c[j-b[i]]!=-1) c[j]=max(c[j], c[j-b[i]]+1); } } for(int i=0;i<id;++i) ss+=b[i]; e.set(0); for(int i=0;i<id;++i) e|=(e<<b[i]); d[0]=1; for(int i=1;i<ss;++i){ d[i]=d[i-1]; if(e.test(i)) ++d[i]; } int ans=1e9; int sum=0; for(int i=0;i<n;++i) sum+=a[i]; int h=0; for(int i=0;i<s;++i){ if(c[i]==-1) continue; int z=bin(max(0, max(sum-i, (k-c[i])*n))); ++h; ans=min(ans, z+i-sum); } bin(8); if(ans>s+ss) cout<<"Impossible"; else cout<<ans<<'\n'; }
#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...