# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
567368 | birthdaycake | Kitchen (BOI19_kitchen) | C++17 | 16 ms | 1048 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL);
using namespace std;
int dp[200001],a[20001],b[200001];
signed main(){
boost;
int n,m,k,sum = 0; cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> a[i]; sum += a[i];
}
if(k == 1){
for(int j = 0; j < m; j++) cin >> b[j];
dp[0] = 1;
for(int i = 0; i < m; i++){
for(int j = 90000; j >= b[i]; j--){
dp[j] += dp[j - b[i]];
}
}
for(int i = sum; i <= 90000; i++){
if(dp[i]){
cout << i - sum;
return 0;
}
}
cout << "Impossible";
return 0;
}
for(int j = 0; j < m; j++) cin >> b[j];
if(m < k){
cout << "Impossible";
return 0;
}
for(int i = 0; i < n; i++){
if(a[i] < k){
cout << "Impossible";
return 0;
}
}
int ans = 1e18;
for(int i = 0; i < (1 << m); i++){
priority_queue<pair<int,int>>x; int tot = 0, good = 1;
for(int j = 0; j < m; j++){
if(i & (1 << j)){
x.push({b[j],j});
tot += b[j];
}
}
for(int j = 0; j < n; j++){
int cnt = 0;
vector<pair<int,int>>d;
while(!x.empty() && cnt < k){
auto y = x.top();
x.pop();
if(y.first){
y.first--;
if(y.first) d.push_back(y);
cnt++;
}else{
good = 0;
}
}
if(cnt < k) good = 0;
for(int f = 0; f < d.size(); f++){
x.push(d[i]);
}
}
if(good){
if(tot >= sum) ans = min(ans,tot - sum);
}
}
if(ans == 1e18){
cout << "Impossible";
return 0;
}
cout << ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |