|
|
Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language
version or invalid test data, or description of the problem is not clear.
Từ tập các bài có trên SPOJ (oi)
6225. Cắt hình chữ nhật
Mã bài: CUTRECT
|
Có một mảnh giấy hình chữ nhật ðược chia ra làm lưới MxN ô vuông ðơn vị.
Nhiệm vụ của bạn là phải cắt mảnh giấy ra làm hai phần thỏa mãn các ðiều kiện sau:
- Ðỉnh trái trên và ðỉnh phải dưới của hình chữ nhật thuộc về hai phần khác nhau.
- Mỗi ô vuông ðơn vị nằm trọn vẹn trong một phần. Nói cách khác, bạn chỉ ðược cắt dọc theo các cạnh của lưới.
Do chi phí ðể cắt mỗi cạnh ðơn vị là khác nhau, bạn cần tìm cách cắt có tổng chi phí của các cạnh mà ðường cắt ði qua là nhỏ nhất.
Hình dưới ðây mô tả hình chữ nhật 2x3 ở ví dụ:
Dữ liệu
- Dòng ðầu ghi 2 số nguyên dương M, N thể hiện lưới có M dòng, mỗi dòng có N ô vuông ðơn vị.(M, N ≤ 400)
- M dòng tiếp theo, mỗi dòng ghi N - 1 số tự nhiên thể hiện chi phí cắt mỗi cạnh dọc.
- M - 1 dòng tiếp theo, mỗi dòng ghi N số tự nhiên thể hiện chi phí cắt mỗi cạnh ngang.
- Chi phí cắt mỗi cạnh nằm trong phạm vi số nguyên 32-bit có dấu. Các cạnh ðược liệt kê theo từng dòng từ trên xuống dưới. Các cạnh thuộc cùng một dòng ðược liệt kê từ trái qua phải.
Kết quả
- Một số tự nhiên duy nhất thể hiện chi phí cắt nhỏ nhất. Nếu không có cách cắt nào thỏa mãn thì in ra -1.
Ví dụ
Input:
2 3
3 1
1 3
3 1 3
Output:
3
Tác giả: Khúc Anh Tuấn
| Được gửi lên bởi: | VOJ Team |
| Ngày: | 2010-03-03 |
| Thời gian chạy: | 3s
|
| Giới hạn mã nguồn: | 50000B |
| Ngôn ngữ cho phép: | Tất cả ngoại trừ: AWK CLOJ ERL F# GO PERL 6 PYTH 3.1.2 SCALA SED TCL |
| Nguồn bài: | VNOI '10 |
|
|
|
|
