#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;
ll q = 0;
void func(vector <ll> temp,ll index){
if (index == m && temp.size() >= k){
vector <ll> temp1;
temp1 = temp;
q++;
bool ok = true;
ll left = 0;
ll c = 0;
while (c < arr.size() && ok){
ll count = 0;
for (int z=0;count<k;z++){
while (temp1[z] == 0 && z < temp1.size()){
z++;
}
if (z == temp1.size()){
ok = false;
break;
}
count++;
temp1[z]--;
}
if (arr[c] < k){
ok = false;
break;
}
left += arr[c]-k;
c++;
}
ll s = 0;
for (int z=0;z<temp1.size();z++){
s += temp1[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);
for (int z=0;z<n;z++){
cin >> arr[z];
}
chef.resize(m);
for (int z=0;z<m;z++){
cin >> chef[z];
}
vector <ll> temp;
func(temp,0);
if (ans == LLONG_MAX){
cout << "Impossible" << endl;
} else {
cout << ans << endl;
}
cout << q << endl;
}
Compilation message
kitchen.cpp: In function 'void func(std::vector<long long int>, ll)':
kitchen.cpp:23:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (index == m && temp.size() >= k){
~~~~~~~~~~~~^~~~
kitchen.cpp:30:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (c < arr.size() && ok){
~~^~~~~~~~~~~~
kitchen.cpp:33:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (temp1[z] == 0 && z < temp1.size()){
~~^~~~~~~~~~~~~~
kitchen.cpp:36:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (z == temp1.size()){
~~^~~~~~~~~~~~~~~
kitchen.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int z=0;z<temp1.size();z++){
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1081 ms |
376 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
