oj.uz

Submission #771602

# Submission time Handle Problem Language Result Execution time Memory
771602 2023-07-03T07:13:24 Z NeroZein Kitchen (BOI19_kitchen) C++17
0 / 100
 83 ms 262144 KB 
#include "bits/stdc++.h"
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 (mx < 0 || mx >= N || occ < 0 || occ >= N || sum < 0 || sum >= N * N || id < 0 || id >= N) {
    cout << "WA" << '\n';
    exit(0); 
  }
  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]; 
  }
  int s2 = 0;
  for (int i = 0; i < m; ++i) {
    cin >> b[i];
    s2 += b[i];
  }
  if (s2 < s) {
    cout << "Impossible" << '\n';
    return 0; 
  }
  for (int i = 0; i < n; ++i) {
    if (a[i] < k) {
      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.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -