← 返回题目列表

AtCoder · icpc2013summer_day3_l

K. 空气污染

中文机器翻译题面 查看原题

20XX年,ICPC(生田电脑污染社区)商圈业主担心空气污染。 为了让城市恢复往日的活力,空气质量必须保持在一定水平以上。

商店街的店铺从1号开始一字排开。 编号为n。 目前,各店铺周边环境清洁度为 pi 。 你从2开始 通过选择n-1商店并循环其周围的气氛,您可以改变该商店和周围商店的气氛的清洁度。 准确地说, i ( 2 \leq i \leq n-1 ) 选择时pi-1和pi+1有 添加pi,反之亦然 减去pi有 添加2pi。换句话说,新的大气之美p'是,

  • p'i-1 = pi-1 + pi

  • p'i = pi - 2 pi

  • p'i+1 = pi+1 + pi 变为。 重复此操作,以提高所有商店的空气清洁度。pi是可接受的最低大气清洁度。 li 目的就是为了达到上述目的。

循环大气需要花费很多钱,所以我们希望尽可能少地进行。 希望大家为ICPC商圈的未来贡献自己的力量。

输入

输入按以下格式给出。

n
p1 ... pn
l1 ... ln

n是商店数量,pi表示i目前店内空气洁净度,li表示i代表商店应达到的氛围洁净度。

约束

输入中的每个变量都满足以下约束。

  • 3 \leq n \leq 105

  • -108 \leq pi \leq 108

  • 1 \leq li \leq 108

输出

每家商店都需要达到空气质量。 在一行上打印大气循环的最少次数。

如果无论你如何操作都无法实现, 输出-1。

示例输入 1

3
3 -1 4
2 1 3

样本输入 1 的输出

1
  • 通过选择商店 2,商店 1、2 和 3 的空气质量将分别为 2、1 和 3。

示例输入 2

3
3 -1 4
2 1 5

样本输入 2 的输出

-1
  • 无论我如何操纵它,Store 3都无法实现清洁空气。

示例输入 3

4
3 -1 -1 3
1 1 1 1

样本输入 3 的输出

3
  • 这可以通过按商店 2、商店 3 和商店 2 的顺序循环气氛来实现。