C11ROOKS - Hai quân xe
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Hai quân xe được đặt tại hai ô khác nhau trên một bàn cờ vua có NxN ô. Mỗi ô của bàn cờ có một giá trị từ 0 đến 1000.
Một ô trong bàn cờ được gọi là bị tấn công nếu ô đó cùng hàng hoặc cùng cột với ít nhất một quân xe. Hai ô vuông có chứa quân xe được xem như không bị tấn công .
Bài toán đặt ra là tìm cách đặt hai quân xe lên bàn cờ, để tổng giá trị các ô bị tấn công là lớn nhất .
Dữ liệu
- Dòng 1: Số nguyên dương N (2 ≤ N ≤ 300).
- N dòng tiếp theo, mỗi dòng gồm N số. Đây là giá trị của các ô trên bàn cờ.
Kết quả
- Tổng lớn nhất tìm được.
Ví dụ
Input 3 0 1 4 3 0 2 1 4 1 Output 15 Input 4 0 1 1 1 1 0 4 3 0 1 3 5 0 0 2 5 Output 23 Input 5 4 2 2 3 3 4 2 1 4 0 1 3 4 0 1 4 3 0 2 3 0 0 3 0 4 Output 40
Giải thích
- Vị trí đặt hai quân xe trong ví dụ 1 là (1, 1) và (2, 2)
- Vị trí đặt hai quân xe trong ví dụ 2 là (1, 3) và (1, 4)
- Vị trí đặt hai quân xe trong ví dụ 3 là (2, 5) và (4, 3)
Giới hạn
- Có 60% số test, 2 ≤ N ≤ 100
- Người up: tohuuquan