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:
C11 Contest Round 22 - Nguyễn Xuân Khánh
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

Hãy đọc nội quy trước khi bình luận.



  • -6
    yanwe111  đã bình luận lúc 19, Tháng 3, 2023, 6:41

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -6
      dylantamau  đã bình luận lúc 19, Tháng 3, 2023, 8:40

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -6
    yanwe111  đã bình luận lúc 19, Tháng 3, 2023, 6:40

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.