Ping Pong (CIIC 2021)


Submit solution


Points: 100 (partial)
Time limit: 4.0s
Memory limit: 128M

Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

Se realizará pronto un torneo de ping pong, en la modalidad dobles: varios equipos, cada uno de 2 jugadores, se enfrentarán entre sí.

El torneo forma parte de un evento benéfico especial, en el cual los equipos de jugadores se forman emparejando entre sí a los mejores N jugadores del país. Para los fines de coordinación del torneo, estos jugadores se numeran desde 1 hasta N.

Los organizadores buscan maximizar el interés del evento resultante, y eso depende de las parejas formadas. Por cada par de jugadores i y j, se conoce un valor a_{i,j} que indica qué tan interesante sería para el público ver competir juntos en un equipo a los jugadores i y j.

El interés total del evento será la suma de los valores a_{i,j} correspondientes a los \frac{N}{2} equipos en los cuales se dividan los N jugadores.

Debes escribir un programa que dado el valor de N y los valores a_{i,j}, determine el máximo interés posible del evento.

Entrada

Se recibe de la entrada estándar en una primera línea, el entero N.

Luego N líneas más, cada una con N enteros separados por espacios. El entero j de la línea i indica el valor a_{i,j}.

Salida

Se debe escribir a la salida estándar una única línea con un único entero: el máximo interés posible del torneo.

Ejemplo

4
0 2 9 5
2 0 4 1
9 4 0 2
5 1 2 0

Salida de Ejemplo

10

Las siguientes son todas las maneras posibles de armar los equipos para este ejemplo:

  • 1-2 y 3-4 : Beneficio 2 + 2 = 4
  • 1-3 y 2-4 : Beneficio 9 + 1 = 10
  • 1-4 y 2-3 : Beneficio 5 + 4 = 9

Restricciones

  • 2 \leq N \leq 30
  • 0 \leq a_{i,j} \leq 10^8
  • a_{i,i} = 0 para 1 \leq i \leq N
  • a_{i,j} = a_{j,i}
  • N siempre es par

Subtareas

  1. (10 puntos) N \leq 8

  2. (20 puntos) N \leq 16

  3. (30 puntos) N \leq 22

  4. (21 puntos) N \leq 28

  5. (19 puntos) N \leq 30


Comments

There are no comments at the moment.