「EZEC-11」Tyres

Luogu

IDLGP8179

Time1000ms

Memory128MB

DifficultyP6

动态规划 DP贪心O2优化枚举洛谷月赛

有 $n$ 套轮胎，滴叉需要用这些轮胎跑 $m$ 圈。使用第 $i$ 套轮胎跑的第 $j$ 圈（对每套轮胎单独计数）需要 $a_i+b_i(j-1)^2$ 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。滴叉需要进入维修站来更换轮胎，所消耗的时间为 $t$ 秒。特别地，滴叉使用的**第一套**轮胎不需要进站更换。为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每圈的时间之和加上进站所花费的时间。 ## Input 第一行输入三个整数 $n,m,t$。接下来 $n$ 行，每行输入两个整数 $a_i,b_i$。 ## Output 输出一个整数，代表总时间的最小值。 [samples] ## Background 这道题曾经有有趣的题目背景。 ## Note **【样例解释】** 对于第一个样例： * 你先让滴叉用第一套轮胎跑一圈，消耗 $10$ 秒。 * 然后进站更换第二套轮胎，消耗 $50$ 秒。 * 然后用第二套轮胎跑三圈。第一圈消耗 $100$ 秒，第二圈消耗 $100+1\times 1^2=101$ 秒，第三圈消耗 $100+1\times 2^2=104$ 秒。 * 总时间为 $10+50+100+101+104=365$ 秒。对于第二个样例，滴叉每圈更换一次新轮胎。注意一套轮胎被卸下后并不会重置它跑的圈数。对于第三个样例，滴叉先使用第一套轮胎跑 $4$ 圈，然后更换第二套轮胎跑 $6$ 圈。 **【数据范围】** **本题采用捆绑测试**。 - Subtask 1（7 pts）：$n=1$。 - Subtask 2（9 pts）：$n\leq10$，$m\leq 100$。 - Subtask 3（13 pts）：$t=0$。 - Subtask 4（21 pts）：保证 $a_i,b_i$ 随机生成。 - Subtask 5（50 pts）：无特殊限制。对于前 $100\%$ 的数据，$1\leq n,b_i\leq 500$，$0\leq t\leq 500$，$1\leq m\leq 2 \times 10^5$，$1\leq a_i\leq 10^9$。

Samples

Input #1

2 4 50
10 100
100 1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "「EZEC-11」Tyres",
    "description": {
      "content": "有 $n$ 套轮胎，滴叉需要用这些轮胎跑 $m$ 圈。 使用第 $i$ 套轮胎跑的第 $j$ 圈（对每套轮胎单独计数）需要 $a_i+b_i(j-1)^2$ 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。 滴叉需要进入维修站来更换轮胎，所消耗的时间为 $t$ 秒。特别地，滴叉使用的**第一套**轮胎不需要进站更换。 为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8179"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有 $n$ 套轮胎，滴叉需要用这些轮胎跑 $m$ 圈。\n\n使用第 $i$ 套轮胎跑的第 $j$ 圈（对每套轮胎单独计数）需要 $a_i+b_i(j-1)^2$ 秒。在本题中，你不需要担心爆胎，安全车，红旗或者不同的比赛策略。\n\n滴叉需要进入维修站来更换轮胎，所消耗的时间为 $t$ 秒。特别地，滴叉使用的**第一套**轮胎不需要进站更换。\n\n为了帮助滴叉拿下 WDC，你需要最小化总时间，总时间等于每...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments