P6766: 地图上的决策

---

【题目描述】

【题目描述】
感谢你为ysc写出了打boss的程序！但是糊涂蛋ysc突然想起来在打boss前还有个更重要的事，他现在和boss不在一个地图！。
为了方便你的编程，ysc把jx3的地图暴力拆解成了一个有n个城市的地图，对于每个城市i只与城市i+1之间存在一条双向道路（既与i相连的城市只有i+1，i-1，编号为1和n的城市除外），通过这条道路需要花费ysc的时间为  ai，每个城市之间存在一位跨城市交通的车夫，车夫可以直接把你送到别的城市而不花费时间，每个城市的车夫的传送半径为 ki（既在i城市的车夫可以把你送到 i+ki 城市，并且不花费时间）如果目标城市大于n则为n。
ysc现在在1号城市，而他需要到n号城市去打boss，并且由于他的贫穷，他在赶路过程中只能使用一次车夫，为了不因为赶路而错过首甲，请你写一个程序告诉他他所需要花费的总时间。
【输入格式】
输入数据包括三行
第一行一个整数n，表示城市数。
第二行n-1个数，表示第i个ai。
第三行n个数，第i个表示城市的车夫的传送半径ki。
【输出格式】
一行一个整数，表示他所花费的时间。
【输入样例】
4 1 2 3 0 0 0 0
【输出样例】
6
【数据范围与提示】
对于50%的数据：1≤n≤310^3，1≤ai≤1×10^5，0≤ki≤3×10^3。
对于100%的数据：1≤n≤310^6，1≤ai≤1×10^12，0≤ki≤3×10^6。
 

题目类型~

冬令营 

咻咻~

提交答案 状态 返回