[JOI 2022 Final] 自学 / Self Study

Luogu

IDLGP8161

Time1000ms

Memory537MB

DifficultyP3

贪心二分2022O2优化JOI（日本）

在 JOI 高中高一的第三个学期的 $M$ 个星期的时间内，有 $N$ 门课，编号为 $1 \sim N$。每个星期有 $N$ 个课时，第 $i$ 个课时上课程 $i$ 的一节课。比太郎是一位高一学生。对于 $N \times M$ 个课时中的每一个，他会选择如下行动中的一个： - 行动 1：比太郎去上课。如果他去上了课程 $i$ 的一节课，那么他对课程 $i$ 的理解程度会增加 $A_i$。 - 行动 2：比太郎不去上课。他转而选择任意一门课，并且自学选中的那门课。如果他选中了课程 $i$ 进行了时长为一课时的自学，那么他对课程 $i$ 的理解程度会增加 $B_i$。一开始，对每门课的理解程度都为 $0$。由于比太郎想要在课后练习算法竞赛，他在非上课时间内不会学习。当第三个学期的所有课时结束后，期末考就会举行。比太郎不想挂科。所以他想要最大化在期末考时对每门课的理解程度的最小值。给定学期的长度，课程的数量，以及对理解程度的提升数值，请写一个程序计算在期末考时对每门课的理解程度的最小值的最大可能值。 ## Input 第一行，两个正整数 $N, M$。第二行，$N$ 个正整数 $A_1, A_2, \ldots, A_N$。第三行，$N$ 个正整数 $B_1, B_2, \ldots, B_N$。 ## Output 输出一行，一个数，表示在期末考时对每门课的理解程度的最小值的最大可能值。 [samples] ## Note **【样例解释 \#1】** 举个例子，如果比太郎按如下方式学习，则他对课程 $1, 2, 3$ 的理解程度将分别为 $19, 18, 19$。 - 第一周课程 $1$ 的课：自学课程 $2$； - 第一周课程 $2$ 的课：自学课程 $2$； - 第一周课程 $3$ 的课：去上课程 $3$ 的课； - 第二周课程 $1$ 的课：去上课程 $1$ 的课； - 第二周课程 $2$ 的课：自学课程 $3$； - 第二周课程 $3$ 的课：去上课程 $3$ 的课； - 第三周课程 $1$ 的课：自学课程 $3$； - 第三周课程 $2$ 的课：自学课程 $2$； - 第三周课程 $3$ 的课：去上课程 $3$ 的课。由于对每门课的最小的理解程度不能大于等于 $19$，输出 $18$。这个样例满足子任务 $3, 5$ 的限制。 **【样例解释 \#2】** 这个样例满足子任务 $1, 3, 5$ 的限制。 **【样例解释 \#3】** 这个样例满足子任务 $3, 5$ 的限制。 **【样例解释 \#4】** 这个样例满足子任务 $2, 3, 4, 5$ 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** 对于 $100 \%$ 的数据，$1 \le N \le 3 \times {10}^5$，$1 \le M \le {10}^9$，$1 \le A_i, B_i \le {10}^9$。 - 子任务 $1$（$10$ 分）：$M = 1$。 - 子任务 $2$（$25$ 分）：$N \cdot M \le 3 \times {10}^5$，$A_i = B_i$。 - 子任务 $3$（$27$ 分）：$N \cdot M \le 3 \times {10}^5$。 - 子任务 $4$（$29$ 分）：$A_i = B_i$。 - 子任务 $5$（$9$ 分）：无特殊限制。 ---- **译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T2「[自習](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t2.pdf) / [Self Study](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t2-en.pdf)」**

Samples

Input #1

3 3
19 4 5
2 6 2

Output #1

Input #2

2 1
9 7
2 6

Output #2

Input #3

5 60000
630510219 369411957 874325200 990002527 567203997
438920902 634940661 593780254 315929832 420627496

Output #3

41397427274960

Input #4

4 25
1 2 3 4
1 2 3 4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[JOI 2022 Final] 自学 / Self Study",
    "description": {
      "content": "在 JOI 高中高一的第三个学期的 $M$ 个星期的时间内，有 $N$ 门课，编号为 $1 \\sim N$。每个星期有 $N$ 个课时，第 $i$ 个课时上课程 $i$ 的一节课。 比太郎是一位高一学生。对于 $N \\times M$ 个课时中的每一个，他会选择如下行动中的一个： - 行动 1：比太郎去上课。如果他去上了课程 $i$ 的一节课，那么他对课程 $i$ 的理解程度会增加 $A_i$",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 549888
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8161"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "在 JOI 高中高一的第三个学期的 $M$ 个星期的时间内，有 $N$ 门课，编号为 $1 \\sim N$。每个星期有 $N$ 个课时，第 $i$ 个课时上课程 $i$ 的一节课。\n\n比太郎是一位高一学生。对于 $N \\times M$ 个课时中的每一个，他会选择如下行动中的一个：\n\n- 行动 1：比太郎去上课。如果他去上了课程 $i$ 的一节课，那么他对课程 $i$ 的理解程度会增加 $A_i$...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments