[ICPC 2024 Xi'an I] Smart Quality Inspector

Luogu

IDLGP10561

Time500ms

Memory512MB

DifficultyP4

2024O2优化ICPC状压 DP西安

Ella has a factory. One day, her factory is facing a product quality inspection. Her factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, and the other $K$ lines are unqualified. The fine of the $i$ -th$(1\leq i\leq K)$ unqualified line is $i$ Yuan. There are $M$ quality inspectors here. For the $j$ -th$(1\leq j\leq M)$ quality inspector, he will inspect from the $l_i$ -th line to the $r_i$ -th line and find the unqualified production line with the largest fine among them, then impose this fine on Ella. Ella does not want to receive so many fines, so she decides to renumber the $N$ production lines to receive the least amount of fines. Please help her. In simple terms: You have a sequence $A$ of length $N$, $A=[1,2,3,...,K,0,0,0,...,0]$. Here $N,K$ are given. There are $M$ pairs of integers, each pair consists of two numbers $l_i,r_i$. You need to rearrange sequence $A$ to minimize the following: $$\sum_{i=1}^M \max_{j=l_i}^{r_i} (A_{j})$$ ## Input The first line contains three integers $N,K,M(1\leq K\leq N\leq 20,1\leq M\leq 10^5)$, described in the statement. Then $M$ lines, the $i$ -th line of them contains two integers $l_i,r_i(1\leq l_i\leq r_i\leq N)$. ## Output An integer indicates the answer. [samples]

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2024 Xi'an I] Smart Quality Inspector",
    "description": {
      "content": "     Ella has a factory. One day, her factory is facing a product quality inspection.                Her factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10561"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ella has a factory. One day, her factory is facing a product quality inspection.\n    \n    \n    \nHer factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, and t...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments