[CERC2019] Light Emitting Hindenburg

Luogu

IDLGP9612

Time1000ms

Memory128MB

DifficultyP3

贪心2019位运算ICPCCERC

Lothar 正在组织他朋友的摇滚乐队的音乐会巡演。巡演将于 11 月举行，每天最多有一场音乐会。这次巡演将非常具有代表性，许多音乐家都愿意参加。巡演中的音乐家人数是严格规定的，不能改变。巡演中的每一场音乐会都必须有所有参加巡演的音乐家参加。对 Lothar 来说，好消息是，候选音乐家的数量至少与巡演中规定的音乐家数量一样多。坏消息是，一个典型的音乐家整个月都没有空，而且各种音乐家的日程安排也大不相同。很久以前，Lothar 编写了一个计算机调度系统的核心，现在他正在利用它来组织这次巡演。他反复地、有点随机地选择一组指定数量的音乐家，并让系统计算出一个可接受的巡演时间表。该系统取决于一种非常具体的数据格式。音乐家的时间表和巡演时间表用数字编码表示。11 月的日子是按月份的数字标记的：$1, 2, \dots, 30$。对于一个给定的音乐家来说，每年 11 月的一天都会被分配一个特定的数字编码。如果音乐家当天空闲，则标签为 $L$ 的一天由整数 $2^{30-L}$ 编码。否则，日期将由 $0$ 编码。音乐家的时间表编码是他或她的所有日期编码的总和。对于一组给定的音乐家来说，每年 11 月的一天都会被分配一个特定的数字编码。如果该组中的所有音乐家当天都空闲，标签为 $L$ 的一天由整数 $2^{30-L}$ 编码。否则，日期将由 $0$ 编码。组的空闲编码是该组所有日期编码的总和。出于许多其他微妙的原因，Lothar 认为最好的巡演应该是任意一组音乐家，这组的空闲编码是可能的最大值。 ## Input 第一行包含两个整数 $N, K\ (1\le K\le N\le 2\times 10^5)$。$N$ 是可用音乐家的数量，$K$ 是参加巡演的音乐家的规定数量。第二行包含一个由 $N$ 个正整数组成的序列。序列中的每个整数表示一个音乐家的时间表编码。编码按任意顺序列出。 ## Output 输出一个整数，代表 $K$ 个音乐家的空闲编码值总和的最大值。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Light Emitting Hindenburg](https://contest.felk.cvut.cz/19cerc/solved/hindenburg.pdf)」**

Samples

Input #1

5 2
6 15 9 666 1

Output #1

Input #2

8 4
13 30 27 20 11 30 19 10

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CERC2019] Light Emitting Hindenburg",
    "description": {
      "content": "Lothar 正在组织他朋友的摇滚乐队的音乐会巡演。巡演将于 11 月举行，每天最多有一场音乐会。这次巡演将非常具有代表性，许多音乐家都愿意参加。巡演中的音乐家人数是严格规定的，不能改变。巡演中的每一场音乐会都必须有所有参加巡演的音乐家参加。 对 Lothar 来说，好消息是，候选音乐家的数量至少与巡演中规定的音乐家数量一样多。坏消息是，一个典型的音乐家整个月都没有空，而且各种音乐家的日程安排也",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9612"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Lothar 正在组织他朋友的摇滚乐队的音乐会巡演。巡演将于 11 月举行，每天最多有一场音乐会。这次巡演将非常具有代表性，许多音乐家都愿意参加。巡演中的音乐家人数是严格规定的，不能改变。巡演中的每一场音乐会都必须有所有参加巡演的音乐家参加。\n\n对 Lothar 来说，好消息是，候选音乐家的数量至少与巡演中规定的音乐家数量一样多。坏消息是，一个典型的音乐家整个月都没有空，而且各种音乐家的日程安排也...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments