제출 #1130497

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130497		m_bezrutchka	Kitchen (BOI19_kitchen)	C++20	0 / 100	473 ms	14692 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];
pair<pair<int,int>,pair<int,int>> pai[MAXN][MAXN][MAXS];
int n, m, k;

void print_path(int r, int c, int s, int x) {
  return;
  if (r != 0 || c != 0) {
    int nr = pai[r][c][s].first.first, nc = pai[r][c][s].first.second, ns = pai[r][c][s].second.first;
    int nx = pai[r][c][s].second.second;
    print_path(nr, nc, ns, nx);
  }
  cout << r << " " << c << " " << s << " " << x << endl;
}

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 << "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]) {
            pai[r][c][s] = {{pr,pc},{s-lo,x}};
            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]) {
            pai[r][c][s] = {{r,c},{s-x,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]) {
      // print_path(k, n, s, 0);
      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;
}

컴파일 시 표준 에러 (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