Submission #1130491

#TimeUsernameProblemLanguageResultExecution timeMemory
1130491m_bezrutchkaKitchen (BOI19_kitchen)C++20
31 / 100
5 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 10;
const int MAXN = 312;

vector<int> a, b;
int resp;
int n, m, k, sum_a;

void try_set(int bm) {
  vector<int> cur;
  for (int i = 0; i < m; i++) {
    if (bm & (1 << i)) {
      cur.push_back(b[i]);
    }
  }
  int lo = 0;
  int cur_r = 0, cur_c = 0;
  int sum_b = 0, sum_rect = 0;
  for (int x: cur) {
    sum_rect += min(x, n);
    sum_b += x;
  }
  // cout << "tested bitmask " << bitset<2>(bm) << endl;
  // cout << "sum_rect = " << sum_rect << " sum_b = " << sum_b << endl;
  int delta = sum_b - sum_a;
  if (sum_rect >= n * k && delta >= 0) {
    resp = min(resp, delta);
  }
}

void solve() {
  resp = INF;
  cin >> n >> m >> k;
  a.resize(n); b.resize(m);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] < k) {
      cout << "Impossible\n";
      return;
    }
    sum_a += a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  int lim = (1LL << m);
  for (int bm = 0; bm < lim; bm++) {
    try_set(bm);
  }
  if (resp == INF) {
    cout << "Impossible\n";
    return;
  }
  cout << resp << "\n";
}

int32_t main() {
  solve();
  return 0;
}
#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...