Submission #1130485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130485		m_bezrutchka	Kitchen (BOI19_kitchen)	C++20	0 / 100	235 ms	2004 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int LLINF = 2e18 + 10;
const int MAXN = 45;
const int MAXS = 1700;

bool dp[MAXN][MAXN][MAXN * MAXN];
int a[MAXN], b[MAXN];

void solve() {
  int n, m, k;
  cin >> n >> m >> k;
  int sum_a = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    sum_a += a[i];
    if (a[i] < k) {
      cout << "Impossible\n";
      return;
    }
  }

  dp[0][0][0] = true;
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
    int x = b[i];
    // cout << "processing x = " << x << endl;
    for (int r = k; r >= 1; r--) {
      for (int c = n; c >= 1; c--) {
        for (int s = MAXS - 1; s >= 0; s--) {
          int pr, pc, lo;
          if (x >= n) {
            if (r == 1) {
              pr = 0;
              pc = 0;
              lo = x - c;
            } else {
              pr = r - 1;
              pc = c;
              lo = x - n;
            }
          } else if (x < c) {
            pr = r;
            pc = x - c;
            lo = 0;
          } else {
            if (r == 1) {
              pr = 0;
              pc = 0;
              lo = x - c;
            } else {
              pr = r - 1;
              pc = n - (x - c);
              lo = 0;
            }
          }
          // printf("r = %lld c = %lld s = %lld checking pr = %lld pc = %lld lo = %lld\n", r, c, s, pr, pc, lo);
          if (lo <= s && pr >= 0 && pc >= 0 && dp[pr][pc][s - lo]) {
            dp[r][c][s] = true;
            // printf("dp[%lld][%lld][%lld] = dp[%lld][%lld][%lld] = true\n", r, c, s, pr, pc, s - lo);
          }
          if (x <= s && dp[r][c][s - x]) {
            dp[r][c][s] = true;
            // printf("2 dp[%lld][%lld][%lld] = dp[%lld][%lld][%lld] = true\n", r, c, s, r, c, s - x);
          }
        }
      }
    }
  }
  int mini = sum_a - k * n;
  for (int s = mini; s < MAXS; s++) {
    if (dp[k][n][s]) {
      cout << s + k * n - sum_a << "\n";
      return;
    }
  }
  cout << "Impossible\n";
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

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