Submit solution
Points:
0.91 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
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
Comments
đừng downvote e huhu
~+1~ downvote ~\rightarrow~ ~-1~ upvote
đừng downvote e huhu