[CSP-X2024 山东] 刷题

Luogu
IDLGB4107
Time1000ms
Memory512MB
DifficultyP3
2024山东CSP-X 小学组
比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。 为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 $n$ 道编程题,将它们从 $1$ 到 $n$ 编号,计划用 $m$ 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。 在小红的计划中,她完成第 $i$ 道题目的时间为 $a_i$。因为题目有难有易,小红做题时可以找好朋友小明帮忙解题,通过询问小明一道题目的解法,可以省去这个题目的做题时间。当然了,小红做题是为了提升自己,而不是提升小明。因此小红决定一天最多求助小明一次。 本题 $m$ 天中,小红做题时间最长一天的总耗时定义为 $T$(小明帮忙做的题目不计入小红的做题总时间)。请你帮小红求出 $T$ 的最小值是多少? ## Input 第一行两个正整数 $n,m$ 分别表示小红做的题目以及小红刷完这些题目计划所用天数。 第二行 $n$ 个正整数,分别表示每个题目解题所用时间 $a_i$。 ## Output 输出仅一行,$m$ 天中耗时最长一天的总耗时 $T$ 的最小值。 [samples] ## Note 对于 $30\%$ 的数据,满足 $1 \leq n \leq 10^3$。 对于 $60\%$ 的数据,满足 $1 \leq n \leq 10^4$。 对于 $100\%$ 的数据,满足 $1 \leq n \leq 10^5,0 \leq a_i \leq 10^4,1 \leq m \leq 1000$。
Samples
Input #1
4 2
1 2 3 3
Output #1
3
Input #2
3 4
999 999 999
Output #2
0
API Response (JSON)
{
  "problem": {
    "name": "[CSP-X2024 山东] 刷题",
    "description": {
      "content": "比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。 为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 $n$ 道编程题,将它们从 $1$ 到 $n$ 编号,计划用 $m$ 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。 在小红的计划中,她完成第 $i$ 道题目的时间为 $a_i$。因为题",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4107"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "比赛之路多艰,做题方得提升。努力刷题的人在比赛中往往能取得很好的成绩,小红就是这样的人。\n\n为了继续提升自己的编程实力,小红整理了一份刷题题单,并选中了题单中的 $n$ 道编程题,将它们从 $1$ 到 $n$ 编号,计划用 $m$ 天时间按照题目编号顺序做完所有的题目(一道题目只能在同一天完成,不可以使用多天完成同一道题目)。\n\n在小红的计划中,她完成第 $i$ 道题目的时间为 $a_i$。因为题...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments