Very Important People
Xem dạng PDF
Gửi bài giải
Điểm:
0,91 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Trong rạp chiếu phim có ~N~ ghế dành cho ~N~ vị khách.
Mỗi người lần lượt vào rạp xem phim và phải ngồi vào đúng chỗ của mình (người vào thứ ~i~ phải ngồi ghế thứ ~i)~.
Tuy nhiên, có một ông khách VIP vào đầu tiên và được giành lấy một ghế bất kì. Mỗi người tiếp theo khi vào rạp thì ý thức hơn nên sẽ ngồi vào đúng chỗ (nếu ghế của họ chưa có người ngồi). Nhưng nếu chỗ của họ đã bị lấy mất thì họ được quyền chọn ~1~ ghế khác bất kì.
Ta biết ~C[i~, ~j]~ là độ hài lòng của vị khách thứ ~i~ khi ngồi vào ghế thứ ~j~. Hãy tính giá trị lớn nhất có thể của tổng độ hài lòng của ~N~ vị khách.
Input
- Dòng đầu tiên là số nguyên dương ~N~ ~(1 \le N \le 1000)~;
- Dòng thứ ~i~ (trong ~N~ dòng tiếp theo) gồm ~N~ số nguyên. Số thứ ~j~ cho là giá trị ~C[i~, ~j]~ ~(|C[i, j]| \le 1\,000\,000\,000)~;
Output
- Một số nguyên duy nhất là tổng lớn nhất có thể đạt được.
Sample Input
4
2 6 8 6
5 0 6 7
8 0 1 9
2 7 2 4
Sample Output
24
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.