Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Dada una secuencia de enteros $a_1, a_2, \cdots, a_n$ de longitud $n$, construimos un grafo no dirigido $G$ a partir de ella. Más precisamente, para todos los $1 \le i < j \le n$, si $i - j = a_i - a_j$, habrá una arista no dirigida en $G$ que conecta los vértices $i$ y $j$. Su peso es $(a_i + a_j)$.

Halla un emparejamiento de $G$ que maximice la suma de los pesos de todas sus aristas e imprime esa suma máxima.

Recuerda que un emparejamiento de un grafo no dirigido consiste en elegir algunas aristas del grafo de modo que ninguna pareja de aristas tenga vértices en común. En particular, no elegir ninguna arista también es un emparejamiento.

Entrada

Hay varios casos de prueba. La primera línea de la entrada contiene un entero $T$ que indica el número de casos de prueba. Para cada caso:

La primera línea contiene un entero $n$ ($2 \le n \le 10^5$) que indica la longitud de la secuencia.

La segunda línea contiene $n$ enteros $a_1, a_2, \cdots, a_n$ ($-10^9 \le a_i \le 10^9$) que indican la secuencia.

Se garantiza que la suma de $n$ de todos los casos de prueba no supera $5 \times 10^5$.

Salida

Para cada caso de prueba, imprime una línea con un entero que indique la máxima suma de los pesos de todas las aristas de un emparejamiento.

Ejemplos

Entrada 1

3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100

Salida 1

30
0
0

Nota

Para el primer caso de prueba del ejemplo, la elección óptima consiste en elegir las tres aristas que conectan los vértices $3$ y $5$, los vértices $4$ y $7$, y los vértices $8$ y $9$. La suma de los pesos es $(5 + 7) + (6 + 9) + (1 + 2) = 30$.

Para el segundo caso de prueba del ejemplo, como todas las aristas tienen pesos negativos, el emparejamiento óptimo no debe elegir ninguna arista. La respuesta es $0$.

Para el tercer caso de prueba del ejemplo, como no hay aristas en el grafo, la respuesta es $0$.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.