Colorful Subsequence

AtCoder

IDabc345_e

Time5000ms

Memory256MB

Difficulty—

There are $N$ balls lined up in a row. The $i$\-th ball from the left is of color $C_i$ and has a value of $V_i$. Takahashi wants to remove **exactly** $K$ balls from this row so that no two adjacent balls have the same color when arranging the remaining balls without changing the order. Additionally, under that condition, he wants to maximize the total value of the balls remaining in the row. Determine if Takahashi can remove $K$ balls so that no two adjacent balls in the remaining row have the same color. If it is possible, find the maximum possible total value of the remaining balls. ## Constraints * $1\leq K<N\leq 2\times 10^5$ * $K\leq 500$ * $1\leq C_i\leq N$ * $1\leq V_i\leq 10^9$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ $C_1$ $V_1$ $C_2$ $V_2$ $\vdots$ $C_N$ $V_N$ [samples]

Samples

Input #1

Output #1

10

After removing the $3$\-rd and $5$\-th balls from the left, the remaining balls are of colors $1, 3, 1$ from left to right, so no two adjacent balls have the same color, satisfying the condition.  
The total value of the remaining balls is $V_1+V_2+V_4=1+5+4=10$.  
There are other ways to remove two balls from the five balls so that no two adjacent balls have the same color, but the total value of the remaining balls is maximized when removing the $3$\-rd and $5$\-th balls.
Hence, print $10$.

Input #2

Output #2

\-1

No matter how you remove one ball, balls of color $1$ will end up next to each other.  
Hence, print $-1$.

Input #3

Output #3

5

Note that exactly $K$ balls must be removed.

API Response (JSON)

{
  "problem": {
    "name": "Colorful Subsequence",
    "description": {
      "content": "There are $N$ balls lined up in a row.   The $i$\\-th ball from the left is of color $C_i$ and has a value of $V_i$. Takahashi wants to remove **exactly** $K$ balls from this row so that no two adjacen",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc345_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ balls lined up in a row.  \nThe $i$\\-th ball from the left is of color $C_i$ and has a value of $V_i$.\nTakahashi wants to remove **exactly** $K$ balls from this row so that no two adjacen...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments