Submission #757798

#TimeUsernameProblemLanguageResultExecution timeMemory
757798taherKitchen (BOI19_kitchen)C++17
72 / 100
1087 ms11260 KiB
#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 maxN = 305;
int a[maxN], b[maxN];
 
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;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    tot += a[i];
    if (a[i] < k) {
      found = true;
    }
  }
  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 (visited[i][sum]) {
      return ;
    }
    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 ;
    }
    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;
}
#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...