Submission #771595

#	Time	Username	Problem	Language	Result	Execution time	Memory
771595		NeroZein	Kitchen (BOI19_kitchen)	C++17	0 / 100	96 ms	262144 KiB

kitchen

#include "bits/stdc++.h"
#define int long long
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int N = 41;

int n, m, k, s;
int a[N], b[N];
int dp[N][N][N][N * N];  //chef, mx, occ, sum
int bt (int id, int mx, int occ, int sum) {
  if (id == m) {
    return (sum < s || mx > 0 ? INT_MAX : sum - s); 
  }
  int& ret = dp[id][mx][occ][sum];
  if (ret != -1) return ret;
  int sub = min(b[id], k);
  int nmx = mx; 
  int nocc = (occ - sub + k) % k;
  if (nocc >= occ) {
    if (mx <= 1) nocc = n, nmx = 0;
    else nmx--;
  }
  deb(id); deb(sub); deb(nmx); deb(nocc); deb(mx); deb(occ); cout << '\n';
  ret = bt(id + 1, mx, occ, sum);
  ret = min(ret, bt(id + 1, nmx, nocc, sum + b[id])); 
  return ret;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m >> k; 
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    s += a[i]; 
    if (a[i] < k) {
      cout << "Impossible" << '\n';
      return 0; 
    }
  }
  int s2 = 0;
  for (int i = 0; i < m; ++i) {
    cin >> b[i];
    s2 += b[i];
  }
  if (s2 < s) {
    cout << "Impossible" << '\n';
    return 0; 
  }
  memset(dp, -1, sizeof dp);
  int ans = bt(0, k, n, 0); 
  if (ans < INT_MAX) {
    cout << ans << '\n';
  } else {
    cout << "Impossible" << '\n';
  }
  return 0;
}

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