Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KVIP - Very Important People

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/kvip


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 <= N <= 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]| <= 1.000.000.000);

Output

  • Một số nguyên duy nhất là tổng lớn nhất có thể đạt được.

Example

Input:
4
2 6 8 6
5 0 6 7
8 0 1 9
2 7 2 4 Output: 24

Được gửi lên bởi:Alex & Friends
Ngày:2013-11-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:C11 Contest Round 22 - Nguyễn Xuân Khánh

hide comments
2015-09-13 14:21:45 Lollipop
test 1 là test gì vậy
2014-12-27 15:51:54 Sue
chỗ ghế ngồi là hoán vị của dãy 1..n :v
chẳng nhẽ đệ quy sinh hoán vị :v
2014-10-12 17:56:15 [$Zeus$]
Đọc ko kĩ đề nên nộp sai mấy phát :P
2014-05-12 18:08:31 Kraken
"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ì."
nói chung là tìm cách ngồi đề độ hài lòng là lớn nhất hay sao nhỉ? Mấy cái câu ở giữa này không hiểu được @@@!
2014-05-10 07:33:59 Anh Duc Le
Ai 75 thì xem lại khởi tạo mảng QHĐ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.