Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Ở quốc gia Alpha, có một khu rừng rất rộng có thể được biểu diễn dưới dạng một lưới các ô vuông có kích thước ~n \times m~ (km). Khu rừng được chia thành các ô vuông kích thước ~1 \times 1~ (km). Ô vuông nằm tại giao của hàng thứ ~i~ và cột thứ ~j~ được ký hiệu là ô ~(i, j)~. Nhà vua đã cử một nhóm lính đi khảo sát khu rừng. Sau khi khảo sát, nhà vua biết được rằng ô ~(i, j)~ hiện có một số cây gỗ với tổng khối lượng là ~a_{ij}~ tấn.

Nhà vua muốn xây dựng một lâu đài trong rừng. Để làm việc này, ông cần vận chuyển toàn bộ gỗ trong rừng đến một ô bất kỳ. Do kỹ thuật lạc hậu, nếu có ~x~ tấn gỗ ở ô ~(i, j)~, nhà vua chỉ có thể thuê một nhóm người vận chuyển ~x~ tấn gỗ này sang một trong các ô ~(i - 1, j)~, ~(i + 1, j)~, ~(i, j - 1)~, ~(i, j + 1)~ với chi phí là ~x~ đồng.

Yêu cầu: Bạn hãy giúp nhà vua tìm tổng chi phí vận chuyển nhỏ nhất có thể để xây dựng lâu đài.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 10^6,\ n \times m \le 10^6)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ gồm ~m~ số nguyên không âm ~a_{i1}, a_{i2}, \ldots, a_{im}~ ~(0 \le a_{ij} \le 10^6)~.

Kết quả

• Một dòng duy nhất là chi phí vận chuyển nhỏ nhất để xây dựng lâu đài.

Subtask

• ~15\%~ số điểm có ~n = 1~ và có không quá 2 ô ~(i, j)~ có ~a_{ij} \gt 0~.
• ~15\%~ số điểm khác có không quá 2 ô ~(i, j)~ có ~a_{ij} \gt 0~.
• ~10\%~ số điểm khác có ~n = 1~ và ~m \le 1000~.
• ~10\%~ số điểm khác có không quá 100 ô ~(i, j)~ có ~a_{ij} \gt 0~.
• ~10\%~ số điểm khác có ~n = 1~ và ~a_{ij} = 1~.
• ~10\%~ số điểm khác có ~n = 1~.
• ~10\%~ số điểm khác có ~a_{ij} = 1~.
• ~10\%~ số điểm khác có ~n \le 100~.
• ~10\%~ số điểm còn lại không có giới hạn gì thêm.

Sample Input 1

2 3
1 2 3
4 5 6

Sample Output 1

20

Giải thích

Ô được chọn để xây lâu đài là ô ~(2, 2)~. Việc vận chuyển gỗ sẽ được thực hiện như sau:

• Vận chuyển 1 tấn gỗ từ ô ~(1, 1)~ đến ô ~(1, 2)~ tốn chi phí là 1.
• Vận chuyển 3 tấn gỗ từ ô ~(1, 3)~ đến ô ~(1, 2)~ tốn chi phí là 3.
• Vận chuyển 4 tấn gỗ từ ô ~(2, 1)~ đến ô ~(2, 2)~ tốn chi phí là 4.
• Vận chuyển 6 tấn gỗ từ ô ~(2, 3)~ đến ô ~(2, 2)~ tốn chi phí là 6.
• Vận chuyển 6 tấn gỗ từ ô ~(1, 2)~ đến ô ~(2, 2)~ tốn chi phí là 6.

Tổng chi phí vận chuyển gỗ là: ~1 + 3 + 4 + 6 + 6 = 20~.

Nguồn: Thi thử HSG9 SQRTOJ 2025 – Ngày 1 Bài 2.