# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
514899 |
2022-01-18T18:23:51 Z |
Mahdi |
Kitchen (BOI19_kitchen) |
C++17 |
|
1 ms |
844 KB |
#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);
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<s;++i)
cout<<c[i]<<' ';
cout<<'\n';
for(int i=0;i<id;++i)
ss+=b[i];
e.set(0);
for(int i=0;i<id;++i)
e|=(e<<a[i]);
d[0]=1;
for(int i=1;i<ss;++i){
d[i]=d[i-1];
if(e[i])
++d[i];
}
int ans=1e9;
int sum=0;
for(int i=0;i<n;++i)
sum+=a[i];
for(int i=0;i<s;++i){
if(c[i]==-1)
continue;
int z=bin(max(0, max(sum-i, (k-c[i])*n)));
ans=min(ans, z+i-sum);
}
if(ans>s+ss)
cout<<"Impossible";
else
cout<<ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |