trang chủ / đề bài / icpc22_mt_e

Bánh sinh nhật

Đề bài

Mô tả

Bob tổ chức sinh nhật cùng bạn bè và muốn cắt chiếc bánh sinh nhật để chia cho mọi người.

Chiếc bánh là một hình chữ nhật kích thước R×C làm từ nhiều loại nguyên liệu. Gọi ai,j là lượng calo của ô ở hàng i, cột j; tổng calo của một miếng bánh là tổng calo các ô của nó.

Bữa tiệc có n người bạn. Vì sợ béo nên họ không muốn ăn quá nhiều: người bạn thứ k chỉ chấp nhận miếng bánh có tổng calo không vượt quá pk.

Bob cắt bánh đúng n−1 lần để được n miếng, theo quy tắc sau:

  • Ở lần cắt thứ l, Bob cắt miếng bánh hiện tại (là một hình chữ nhật) theo chiều ngang hoặc chiều dọc, dọc theo đường kẻ giữa các ô, thành hai miếng hình chữ nhật, mỗi miếng có kích thước ít nhất 1×1.
    • Nếu cắt ngang, miếng phía trên được đưa cho người bạn thứ l, miếng phía dưới được dùng cho lần cắt tiếp theo.
    • Nếu cắt dọc, miếng bên trái được đưa cho người bạn thứ l, miếng bên phải được dùng cho lần cắt tiếp theo.
  • Sau n−1 lần cắt, miếng còn lại được đưa cho người bạn thứ n, không thừa phần nào.
  • Miếng bánh của người bạn thứ l phải có tổng calo không vượt quá pl.

Ví dụ với n=3, p=[5,10,15] và chiếc bánh 2×2 có hàng trên là 1,5 và hàng dưới là 2,8:

  • Cách 1: cắt ngang trước, người thứ nhất nhận hàng trên (1+5=6), phần còn lại 2,8 được cắt dọc thành 2 và 8. Các miếng có calo [6,2,8], không hợp lệ vì 6>5.
  • Cách 2: cắt dọc trước, người thứ nhất nhận cột trái (1+2=3), phần còn lại là cột 5,8 được cắt ngang thành 5 và 8. Các miếng có calo [3,5,8], thỏa mãn cả ba người.

Hãy đếm số cách cắt bánh khác nhau tuân theo quy tắc và làm hài lòng tất cả mọi người. Hai cách khác nhau nếu ở một lần cắt nào đó chúng khác hướng cắt hoặc khác vị trí cắt.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên R, C và n (1≤R,C≤100, 1≤n≤min(10,R+C−1)).

Mỗi dòng trong R dòng tiếp theo chứa C số nguyên ai,j (0≤ai,j≤100).

Dòng cuối cùng chứa n số nguyên p1,p2,…,pn (0≤pk≤106).

Dữ liệu ra

In ra số cách cắt bánh thỏa mãn, chia lấy dư cho 109+7.

Ràng buộc

  • 1≤R,C≤100, 1≤n≤min(10,R+C−1).
  • 0≤ai,j≤100.
  • 0≤pk≤106.

Ví dụ

Input Output Giải thích
2 2 3
1 5
2 8
5 10 15
1 Chỉ có cách 2 ở trên là hợp lệ.
3 3 2
10 8 6
8 4 10
1 1 0
78 25
3 Cắt ngang sau hàng 1 (các miếng 24, 24), cắt ngang sau hàng 2 (46, 2) hoặc cắt dọc sau cột 2 (31, 16).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0