Hàng chờ tắm

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Trong một ký túc xá có một phòng tắm duy nhất. Mỗi sáng có 5 sinh viên (đánh số từ $1$ đến $5$ ) xếp hàng chờ trước cửa phòng tắm. Khi phòng tắm mở, người đầu hàng vào tắm; tắm xong người đó rời đi, người tiếp theo trong hàng vào tắm, và cứ thế cho đến hết.

Trong lúc đợi, các sinh viên trò chuyện với nhau. Tại mỗi thời điểm (trước khi phòng tắm mở, và trong khi mỗi lần một người đang tắm), người ở vị trí $2 i - 1$ trong hàng hiện tại nói chuyện với người ở vị trí $2 i$ . Nếu số người trong hàng lẻ thì người cuối hàng không nói chuyện với ai.

Nếu sinh viên $i$ và sinh viên $j$ nói chuyện với nhau thì độ vui của sinh viên $i$ tăng $g_{i j}$ và độ vui của sinh viên $j$ tăng $g_{j i}$ . Hai sinh viên có thể nói chuyện với nhau nhiều lần — mỗi lần đều được cộng độ vui như trên.

Cho ma trận $g$ kích thước $5 \times 5$ . Hãy tìm thứ tự xếp hàng ban đầu sao cho tổng độ vui của cả 5 sinh viên sau khi mọi người tắm xong là lớn nhất, và in ra giá trị tổng đó.

Dữ liệu vào

5 dòng, mỗi dòng gồm 5 số nguyên cách nhau bởi dấu cách: số thứ $j$ trên dòng $i$ là $g_{i j}$ ( $0 \leq g_{i j} \leq 10^{5}$ ). Đảm bảo $g_{i i} = 0$ với mọi $i$ .

Dữ liệu ra

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

Ràng buộc

$0 \leq g_{i j} \leq 10^{5}$
$g_{i i} = 0$ với mọi $i$

Ví dụ

Input	Output	Giải thích
0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0	32	Thứ tự tối ưu là $2, 3, 1, 5, 4$ . Cặp $(1, 5)$ nói chuyện hai lần và cặp $(5, 4)$ nói chuyện hai lần, các cặp khác đều có $g = 0$ . Tổng $= 2 \cdot (9 + 7) + 0 = 32$ .
0 43 21 18 2 3 0 21 11 65 5 2 0 1 4 54 62 12 0 99 87 64 81 33 0	620	Duyệt qua tất cả $5! = 120$ hoán vị, thứ tự cho tổng độ vui lớn nhất là $620$ .

Bình luận

Không có bình luận tại thời điểm này.