「PEOI Rd1」寻宝(treasure)

Luogu
IDLGP9225
Time1000ms
Memory256MB
DifficultyP6
动态规划 DPO2优化斜率优化
有一天 wrzSama 在寻宝,突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器,第 $i$ 个机器可以生产 $2^i$ 个钻石。 具体地,wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器,让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质,每当他用一次第 $i$ 个机器后,会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻石时就需要 $a_i + b_i$ 的时间,每次不断累加,第 $x$ 次开动就需要 $a_i+(x-1)b_i$ 的时间。 wrzSama 需要得到至少 $2^n$ 个钻石来得到宝藏,请问他最少需要多长时间。 ## Input 第一行一个正整数 $n$。 第二行 $n$ 个正整数,表示 $a_1,a_2,\dots,a_n$。 第三行 $n$ 个正整数,表示 $b_1,b_2,\dots,b_n$。 ## Output 一行一个正整数,即为答案。 [samples] ## Note #### 样例解释 样例 1 解释:直接获得 $2^3$,花费 3 的时间。 样例 2 解释:获得 2 个 $2^1$,花费 3 的时间,然后再花 2 的时间获得一个 $2^2$,这样 wrzSama 就可以得到 $2 \times 2^1 + 2^2 = 8 = 2^n$ 了。 样例 3 解释:获得 2 个 $2^1$ 和 3 个 $2^2$。 --- #### 数据范围 **本题采用捆绑测试。** |子任务|分值|特殊限制| |:-:|:-:|:-:| |$1$|$16$|$1 \leq n \leq 10$| |$2$|$16$|$1 \leq n \leq 20$| |$3$|$24$|$1 \leq a_i \leq 3 \times 10^3$| |$4$|$44$|无| 对于 $100\%$ 的数据,保证 $1 \le n \le 10^3$,$1 \le a_i,b_i \le 10^7$。
Samples
Input #1
3
1 2 3
3 2 1
Output #1
3
Input #2
3
1 2 100
1 2 1
Output #2
5
Input #3
4
1 2 100 100
1 2 1 1
Output #3
15
API Response (JSON)
{
  "problem": {
    "name": "「PEOI Rd1」寻宝(treasure)",
    "description": {
      "content": "有一天 wrzSama 在寻宝,突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器,第 $i$ 个机器可以生产 $2^i$ 个钻石。 具体地,wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器,让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质,每当他用一次第 $i$ 个机器后,会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9225"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一天 wrzSama 在寻宝,突然他掉到了一个神奇的房间里。这个房间里有 $n$ 个机器,第 $i$ 个机器可以生产 $2^i$ 个钻石。\n\n具体地,wrzSama 可以用 $a_i$ 的时间开动第 $i$ 个机器,让它生产 $2^i$ 个钻石。这些机器有个很特殊的性质,每当他用一次第 $i$ 个机器后,会让它的开动时间 $a_i$ 加上 $b_i$。这意味着当他要第二次得到这 $2^i$ 个钻...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments