#P11652. [COCI 2024/2025 #4] 鞋 / Cipele(疑似错题)

[COCI 2024/2025 #4] 鞋 / Cipele(疑似错题)

题目背景

译自 COCI 2024/2025 #4 T4。2s,0.5G\texttt{2s,0.5G}。满分为 120120

根据讨论,本题为错题,可能不存在靠谱做法。

题目描述

nn 双鞋,标号 1n1\sim n。鞋柜是一个栈,初始鞋都在鞋柜中,从栈顶到栈底依次是第 1,2,,n1,2,\ldots,n 双鞋。

接下来 qq 天,第 ii 天要穿标号为 aia_i 的鞋。如果这双鞋是栈顶到栈底第 jj 双鞋,则需要 jj 秒将其拿出(不改变其他鞋的相对顺序);如果这双鞋在走廊里,则不花费时间。

每天结束时,可以选择将标号为 aia_i 的鞋入栈,或者放在走廊里。走廊里至多能放 mm 双鞋。

额外地,除了取鞋的过程中,随时都可以从走廊取任意多双鞋(以任意顺序)入栈。

试最小化取鞋用的总时间。

输入格式

第一行,三个整数 n,m,qn,m,q

第二行,qq 个正整数 a1,a2,,aqa_1,a_2,\ldots,a_q

输出格式

输出一行一个正整数,表示答案。

5 1 6
2 1 2 1 2 1
5
6 0 4
5 4 3 4
17
3 2 7
1 2 3 2 3 1 3
4

提示

样例解释

样例 11 解释:第 11 天时取第 22 双鞋并放在走廊。穿完第 11 双鞋后立刻放入栈中。不难发现这样只需要 2+1+0+1+0+1=52+1+0+1+0+1=5 秒。

提示

对于 100%100\% 的数据,保证:

  • 1n2×1051\le n\le 2\times 10^5
  • 0m2×1050\le m\le 2\times 10^5
  • 1q1061 \le q\le 10^6
  • 1ain1\le a_i\le n
子任务编号 n,mn,m\le qq\le 特殊性质 得分
1 1 10310^3 17 17
2 2 2×1052\times 10^5 10610^6 A 27 27
3 3 B 37 37
4 4 2×1052\times 10^5 24 24
5 5 10610^6 15 15
  • 特殊性质 A:n=mn=m
  • 特殊性质 B:m=0m=0