#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
ll n,m,k;
ll ans = LLONG_MAX;
vector <ll> chef;
vector <ll> arr;
void func(vector <ll> temp,ll index){
if (index == m && temp.size() >= k){
bool ok = true;
ll left = 0;
ll c = 0;
while (c < arr.size() && ok){
sort(temp.rbegin(),temp.rend());
ll count = 0;
for (int z=0;count<k;z++){
while (temp[z] == 0 && z < temp.size()){
z++;
}
if (z == temp.size()){
ok = false;
break;
}
count++;
temp[z]--;
}
if (arr[c] < k){
ok = false;
break;
}
left += arr[c]-k;
c++;
}
ll s = 0;
for (int z=0;z<temp.size();z++){
s += temp[z];
}
if (s >= left && ok) ans = min(ans,s-left);
return;
}
if (index == m) return;
func(temp,index+1);
temp.push_back(chef[index]);
func(temp,index+1);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m >> k;
arr.resize(n);
ll s = 0;
for (int z=0;z<n;z++){
cin >> arr[z];
s += arr[z];
}
chef.resize(m);
for (int z=0;z<m;z++){
cin >> chef[z];
}
if (k == 1){
bitset<90001> dp[m];
vector <bool> ok(90001,false);
for (int z=0;z<m;z++){
dp[z][0] = true;
}
dp[0][chef[0]] = true;
for (int z=1;z<m;z++){
for (int x=0;x<=90000;x++){
if (dp[z-1][x] && x+chef[z] <= 90000) {
dp[z][x+chef[z]] = true;
ok[x+chef[z]] = true;
}
}
}
ll ans = -1;
ll c = 0;
for (int z=s;z<=90000;z++){
if (ok[z]) {
ans = z;
break;
}
c++;
}
if (ans == -1) cout << "Impossible" << endl;
else cout << ans-s << endl;
return 0;
}
vector <ll> temp;
func(temp,0);
if (ans == LLONG_MAX){
cout << "Impossible" << endl;
} else {
cout << ans << endl;
}
}
Compilation message
kitchen.cpp: In function 'void func(std::vector<long long int>, ll)':
kitchen.cpp:22:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (index == m && temp.size() >= k){
~~~~~~~~~~~~^~~~
kitchen.cpp:26:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (c < arr.size() && ok){
~~^~~~~~~~~~~~
kitchen.cpp:30:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (temp[z] == 0 && z < temp.size()){
~~^~~~~~~~~~~~~
kitchen.cpp:33:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (z == temp.size()){
~~^~~~~~~~~~~~~~
kitchen.cpp:48:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int z=0;z<temp.size();z++){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
33 ms |
3192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1060 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
