Submission #1130491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130491		m_bezrutchka	Kitchen (BOI19_kitchen)	C++20	31 / 100	5 ms	328 KiB

kitchen

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28