[LSOT-2] 胜者组

Luogu

IDLGP10156

Time1000ms

Memory1024MB

DifficultyP4

动态规划 DP背包 DP

小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\times|i-j|$ 的不满意度。这里 $x$ 是输入一开始给定的常数。你需要让学生的不满意度最小化，或报告无法留下不多于 $m$ 个学习信息学的学生。 ## Input 第一行四个正整数 $n,m,k,x$。接下来两行每行 $n$ 个整数分别表示 $a_i,c_i$。 ## Output 一行一个整数表示最小的不满意度。或输出 `Impossible` 表示无解。 [samples] ## Background 进入胜者组就算胜利吗... 至少人们都这样说。 ## Note 样例解释：分别钦定 $(1,2)$ 和 $(4,6)$ 学习文化课，不满意度为 $(2+5+3\times|1-2|)+(2+7+3\times|4-6|)=25$。需要注意的是，一个同学不可以被钦定多次。 **「本题采用捆绑测试」** - $\texttt{Subtask 1(15pts)：}n\le20$。 - $\texttt{Subtask 2(15pts)：}x=0$。 - $\texttt{Subtask 3(15pts)：}k=1$。 - $\texttt{Subtask 4(20pts)：}n\le 300$。 - $\texttt{Subtask 5(35pts)：}$无特殊性质。对于全部的数据，$0\le a_i,x\le10^5$，$1\le c_i\le k\le n\le 5000$，$0\le m\le n$。

Samples

Input #1

6 2 2 3
2 5 7 2 5 7
1 1 2 1 2 1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[LSOT-2] 胜者组",
    "description": {
      "content": "小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。 具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。 学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。 你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\\times|i-",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10156"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。\n\n具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。\n\n学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。\n\n你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\\times|i-...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments