제출 #757807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757807		taher	Kitchen (BOI19_kitchen)	C++17	100 / 100	576 ms	11292 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 maxN = 305;
int a[maxN], b[maxN], long_ids[maxN], short_ids[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;

  if (!found) {
    int ptr_long = 0, ptr_short = 0;

    for (int i = 0; i < m; i++) {
      if (b[i] >= n) {
        long_ids[ptr_long++] = i;
      } else {
        short_ids[ptr_short++] = i;
      }
    }
   
    ndp[0] = 1;
    for (int i = 0; i < ptr_long; 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 == ptr_short) {
        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);
        }
        visited[i][sum] = true;
        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: 28 / 28