Submission #1130500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130500		m_bezrutchka	Kitchen (BOI19_kitchen)	C++20	0 / 100	1095 ms	1152 KiB

kitchen

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

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

bool dp[MAXN][MAXN][MAXS];
int a[MAXN], b[MAXN];
int n, m, k;

void solve() {
  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 << "\n\n\n\nprocessing 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--) {
          for (int rect = 0; rect <= min(n, x); rect++) {
            int nc = c - rect, nr = r;
            if (nc <= 0) {
              nr--;
              nc += n;
              if (nr == 0) {
                nc = 0;
              }
            }
            int ns = s - (x - rect);
            if (ns >= 0 && nr >= 0 && nc >= 0 && dp[nr][nc][ns]) {
              dp[r][c][s] = true;
            }
          }
        }
      }
    }
  }
  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;
}

Compilation message (stderr)

kitchen.cpp:4:24: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
    4 | const int LLINF = 2e18 + 10;
      |                   ~~~~~^~~~

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