codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2248C.md (2419B)


      1 Source: https://codeforces.com/problemset/problem/2248/C
      2 
      3 C. Maximize the Score
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given an array $a$ of length $2n$. Each integer from $1$ to $n$ occurs exactly twice in $a$.
     22 
     23 Initially, your score is $0$.
     24 
     25 You can repeatedly perform the following operation while $a$ is non-empty:
     26 
     27 * Choose an integer $x$ that is present in $a$.
     28 * Let $l$ and $r$ be the indices of the leftmost and rightmost occurrences of $x$ in the current array, respectively. If $x$ occurs only once, then $l = r$.
     29 * Add $(r - l + 1)^2$ to your score.
     30 * Delete the elements $a_l, a_{l + 1}, \ldots, a_r$ from $a$. The remaining elements are concatenated without changing their order and re-indexed starting from $1$.
     31 
     32 Find the maximum possible score after making the array empty.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     37 
     38 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     39 
     40 The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \le a_i \le n$).
     41 
     42 It is guaranteed that each integer from $1$ to $n$ occurs exactly twice in $a$.
     43 
     44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     45 
     46 Output
     47 
     48 For each test case, output a single integer — the maximum possible score.
     49 
     50 Example
     51 
     52 Input
     53 
     54 ```
     55 6
     56 
     57 1
     58 
     59 1 1
     60 
     61 2
     62 
     63 1 2 1 2
     64 
     65 2
     66 
     67 1 2 2 1
     68 
     69 3
     70 
     71 1 1 2 3 3 2
     72 
     73 3
     74 
     75 1 2 3 3 2 1
     76 
     77 4
     78 
     79 1 2 3 4 1 2 3 4
     80 ```
     81 
     82 Output
     83 
     84 ```
     85 4
     86 
     87 10
     88 
     89 16
     90 
     91 20
     92 
     93 36
     94 
     95 28
     96 ```
     97 
     98 Note
     99 
    100 In the second test case, one optimal strategy is to choose $x = 1$ first. This deletes the subarray $[1, 2, 1]$ and adds $3^2 = 9$ to the score. The remaining array is $[2]$; choosing $x = 2$ adds $1$. The total score is $10$.
    101 
    102 In the third test case, choosing $x = 1$ deletes the whole array and adds $4^2 = 16$ to the score.
    103 
    104 In the fourth test case, choose $x = 1$ first and then choose $x = 2$. The total score is $2^2 + 4^2 = 20$.
    105 
    106 In the sixth test case, choose $x = 2$ first. This deletes the subarray $[2, 3, 4, 1, 2]$ from the middle of the array and adds $5^2 = 25$ to the score. After deleting this subarray and concatenating the remaining elements, the array becomes $[1, 3, 4]$. Choosing each of the three remaining values then adds $1$, so the total score is $28$.