Submission #757790

#	Time	Username	Problem	Language	Result	Execution time	Memory
757790		taher	Kitchen (BOI19_kitchen)	C++17	72 / 100	1082 ms	11248 KiB

kitchen

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
using namespace std;
 
const int N = 300 * 300 + 5;
bool visited[305][N];
int ndp[N];
 
const int inf = 1000000000;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  bool found = false;
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> a(n);
  int tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    tot += a[i];
    if (a[i] < k) {
      found = true;
    }
  }
  vector<int> b(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  int ans = inf;
  vector<int> long_ids;
  vector<int> short_ids;
  for (int i = 0; i < m; i++) {
    if (b[i] >= n) {
      long_ids.push_back(i);
    } else {
      short_ids.push_back(i);
    }
  }

  ndp[0] = 1;
  for (int i = 0; i < (int) long_ids.size(); i++) {
    for (int it = N - 1 - b[long_ids[i]]; it >= 0; it--) {
      if (ndp[it] > 0) {
        ndp[it + b[long_ids[i]]] = max(ndp[it + b[long_ids[i]]], ndp[it] + 1);
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if (ndp[i] > 0) --ndp[i];
  }
  function<void(int, int)> Rec = [&](int i, int sum) {
    if (i == (int) short_ids.size()) {
      if (sum >= max(n * k, tot)) {
        ans = min(ans, sum - tot);
        return ;
      }
      int ptr = tot - sum;
      while (ptr < N && sum + n * ndp[ptr] < n * k) ptr++;
      if (ptr < N && ndp[ptr] > 0) {
        ans = min(ans, sum + ptr - tot);
      }
      return ;
    }
    if (visited[i][sum]) {
      return ;
    }
    Rec(i + 1, sum + b[short_ids[i]]);
    Rec(i + 1, sum);
    visited[i][sum] = true;
    return ;
  };
 
  Rec(0, 0);
  if (ans < inf && !found) {
    cout << ans << '\n';
  } else {
    cout << "Impossible\n";
  }
  return 0;
}

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