{"problem":{"name":"[蓝桥杯 2020 省 AB3] 旅行家","description":{"content":"从前，在海上有 $n$ 个岛屿，编号 $1$ 至 $n$。居民们深受洋流困扰，无法到达比自己当前所在岛屿编号更小的岛屿。经过数年以后，岛屿上的人数随着岛屿的编号递增（可能相等）。作为一名出色的旅行家（$\\mathrm{RP}$ 学家），你想从 $1$ 号岛屿出发开启一次旅程，以获得更多的 $\\mathrm{RP}$，因为受到海洋的洋流影响，你只能去到比当前岛屿编号更大的岛屿。因为你比较善良，你会在","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8726"},"statements":[{"statement_type":"Markdown","content":"从前，在海上有 $n$ 个岛屿，编号 $1$ 至 $n$。居民们深受洋流困扰，无法到达比自己当前所在岛屿编号更小的岛屿。经过数年以后，岛屿上的人数随着岛屿的编号递增（可能相等）。作为一名出色的旅行家（$\\mathrm{RP}$ 学家），你想从 $1$ 号岛屿出发开启一次旅程，以获得更多的 $\\mathrm{RP}$，因为受到海洋的洋流影响，你只能去到比当前岛屿编号更大的岛屿。因为你比较善良，你会在离开一个岛屿的时候将你的 $\\mathrm{RP}$ 分散给岛民，具体地：你的 $\\mathrm{RP}$ 会除以 $2$（用去尾法取整，或者说向零取整）（当你的 $\\mathrm{RP}$ 小于零时，岛民也依旧要帮你分担，毕竟你们已经建立起了深厚的友谊)。\n\n第 $i$ 号岛屿有 $T_{i}$ 人，但是你很挑剔，每次你从 $j$ 号岛屿到达 $i$ 号岛屿时，你只会在到达的岛屿上做 $T_{i} \\times T_{j}$ 件好事（一件好事可以获得 $1$ 点 $\\mathrm{RP}$ )。\n\n唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 $i$ 号岛屿的住宿扣除 $F_{i}$ 点 $\\mathrm{RP}$。\n\n注意: 将离开一个岛屿时，先将 $\\mathrm{RP}$ 扣除一半，再扣除住宿的 $\\mathrm{RP}$，最后在新到达的岛屿上做好事，增加 $\\mathrm{RP}$。离开 $1$ 号岛屿时需要扣除在 $1$ 号岛屿住宿的 $\\mathrm{RP}$，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 $\\mathrm{RP}$ 。\n\n你因为热爱旅行（RP），所以从 $1$ 号岛屿开始旅行，初始时你有 $0$ 点 $\\mathrm{RP}$。你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 $\\mathrm{RP}$ 值是多少?\n\n## Input\n\n输入的第一行包含一个数 $n$，表示岛屿的总数。\n\n第二行包含 $n$ 个整数 $T_{1},T_{2},\\cdots,T_{n}$，表示每个岛屿的人口数。\n\n第三行包含 $n$ 个整数 $F_{1},F_{2},\\cdots,F_{n}$，表示每个岛屿旅馆损失的 $\\mathrm{RP}$。 \n\n## Output\n\n输出一个数，表示最大获得的 $\\mathrm{RP}$ 值。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n从一号岛屿直接走到三号岛屿最优，初始 $0$ 点 $\\mathrm{RP}$，扣除一半取整变成 $0$ 点。扣除在一号节点住宿的 $1 \\mathrm{RP}$，在三号岛屿做好事产生 $4 \\times 5=20$ 点 $\\mathrm{RP}$。最终得到 $19$ 点 $R P$ 。\n\n**【评测用例规模与约定】**\n\n对于 $20 \\%$ 的评测用例，$1 \\leq n \\leq 15$;\n\n对于 $70 \\%$ 的评测用例，$1 \\leq n \\leq 5000$;\n\n对于所有评测用例，$1 \\leq n \\leq 5\\times10^5,1 \\leq T_{i} \\leq 20000,1 \\leq F_{i} \\leq 2\\times 10^8$。给定的 $T_{i}$ 已经按照升序排序。\n\n建议使用 64 位有符号整数进行运算。\n\n蓝桥杯 2020 第三轮省赛 AB 组 J 题。\n\nUpd.2024.7.13 已添加hack数据","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8726","tags":["动态规划 DP","2020","斜率优化","蓝桥杯省赛","李超线段树"],"sample_group":[["3\n4 4 5\n1 10 3","19"],["5\n969 980 1013 1016 1021\n888423 945460 865822 896150 946615","246172"]],"created_at":"2026-03-03 11:09:25"}}