trang chủ / đề bài / icpcwf17_c

Nhiệm vụ bất khả thi

Đề bài

Mô tả

Một ngày nắng đẹp mùa xuân, bạn hẹn gặp Patrick, một người bạn thân và cũng là đồng phạm cũ. Patrick đã thua gần hết tiền vì cá cược vào các cuộc thi lập trình, nên anh cần thực hiện thêm một phi vụ nữa. Để làm việc này anh cần bạn giúp, dù bạn đã rửa tay gác kiếm. Lúc đầu bạn ngần ngại, vì bạn không hề muốn quay lại con đường phạm tội, nhưng bạn nghĩ nghe thử kế hoạch của anh thì cũng chẳng hại gì.

Trong một nhà kho gần đó có một lô hàng thiết bị tiêu dùng đắt tiền, và Patrick định lấy trộm càng nhiều càng tốt. Việc này đòi hỏi tìm đường vào tòa nhà, vô hiệu hóa bảo vệ, vượt qua nhiều hàng rào tia laser: những kỹ thuật quen thuộc của một vụ trộm. Tuy nhiên, khu vực trung tâm của nhà kho được trang bị một hệ thống an ninh mà Patrick không thể vô hiệu hóa. Đây là lúc anh cần bạn giúp.

Hàng được đựng trong các thùng hình lập phương lớn, tất cả có cùng kích thước. Các thùng được xếp thành những chồng ngay ngắn, tạo thành một lưới ba chiều. Mỗi giờ hệ thống an ninh chụp ảnh các chồng thùng bằng ba camera: camera phía trước, camera bên cạnh và camera phía trên. Ảnh từ camera phía trước cho thấy chiều cao của chồng cao nhất trong mỗi cột, ảnh từ camera bên cạnh cho thấy chiều cao của chồng cao nhất trong mỗi hàng, còn ảnh từ camera phía trên cho thấy mỗi ô có chồng thùng hay đang trống. Nếu hệ thống an ninh phát hiện bất kỳ ảnh nào thay đổi, chuông báo động sẽ reo.

Khi đã vào trong, Patrick sẽ xác định chiều cao của các chồng thùng và gửi cho bạn. Hình dưới đây là một cách xếp có thể có của lưới cùng ảnh chụp từ mỗi camera (từ trái sang: lưới chiều cao, ảnh phía trước, ảnh bên cạnh, ảnh phía trên).

Patrick muốn lấy trộm càng nhiều thùng càng tốt. Vì không thể vô hiệu hóa hệ thống an ninh, anh định đánh lừa nó bằng cách sắp xếp lại các thùng còn lại thành các chồng sao cho lần chụp tiếp theo cho ra đúng những bức ảnh như cũ. Trong ví dụ trên, có thể lấy trộm 9 thùng. Lưới dưới đây là một cách xếp sau vụ trộm mà hệ thống an ninh không thể phân biệt với ban đầu.

grid
1 4 0 5 1
2 1 1 0 1
0 1 3 1 4
0 3 0 1 1
2 1 1 1 1

Patrick nhờ bạn xác định số thùng lớn nhất có thể lấy trộm mà vẫn để lại một cách xếp đánh lừa được hệ thống an ninh. Bạn có giúp anh thực hiện phi vụ cuối cùng này không?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên r và c, lần lượt là số hàng và số cột của lưới. Mỗi dòng trong r dòng tiếp theo chứa c số nguyên, là chiều cao (tính theo số thùng) của các chồng trong hàng tương ứng.

Dữ liệu ra

In ra số thùng lớn nhất có thể lấy trộm mà không bị phát hiện.

Ràng buộc

  • 1≤r≤100, 1≤c≤100.
  • Mọi chiều cao nằm trong đoạn [0,109].

Ví dụ

Input Output Giải thích
5 5
1 4 0 5 2
2 1 2 0 1
0 2 3 4 4
0 3 0 3 1
1 2 2 1 1
9 Đây là lưới trong hình. Ban đầu có 45 thùng, lưới sau vụ trộm ở trên còn 36 thùng: chiều cao lớn nhất của mỗi hàng (5,2,4,3,2), của mỗi cột (2,4,3,5,4) và tập các ô trống đều giữ nguyên.
2 3
50 20 3
20 10 3
30 Xếp lại thành lưới 50 1 3 / 1 20 1: chồng cao 20 đặt ở ô hàng 2 cột 2 giữ được chiều cao lớn nhất của cả hàng 2 lẫn cột 2. Còn lại 76 thùng, lấy được 106−76=30 thùng.

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