B - Footsteps in the Hallway Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、N 枚のタイルが一列に並んだ長い廊下を通り抜けようとしています。タイルは左から順にタイル 1, タイル 2, \ldots, タイル N と番号が付けられています。

各タイルにはほこりが積もっており、タイル i には初め H_i の厚さのほこりが積もっています。高橋君がタイル i を踏むと、そのタイルのほこりの厚さは \max(0,\; H_i - D_i) になります。ここで D_i はタイル i に対して定められた非負整数です。高橋君が踏まなかったタイルのほこりの厚さは初期の厚さ H_i のまま変化しません。

高橋君はタイル 1 からスタートし、タイル N がゴールです。高橋君は常に右方向にのみ進みます。具体的には、現在タイル j にいるとき、次の移動先としてタイル j+1 またはタイル j+2 を選べます。ただし、タイル N を超える位置には移動できません（j+1 \leq N のときのみタイル j+1 に、j+2 \leq N のときのみタイル j+2 に移動できます）。高橋君は移動先のタイルに到着した時点でそのタイルを踏みます。スタート地点であるタイル 1 も踏みます。高橋君はタイル N に到達した時点で移動を終了します。

以上の移動ルールにより、タイル 1 とタイル N は必ず踏まれます。また、高橋君は常に右方向に進むため、同じタイルを 2 回以上踏むことはありません。

高橋君が廊下を通り抜けた後、青木君が廊下を調べ、足跡が残っているタイルの数を数えます。タイル i に足跡が残っているとは、高橋君の移動終了後のタイル i のほこりの厚さが初期の厚さ H_i より真に小さくなっていることを意味します。

  • 高橋君がタイル i を踏まなかった場合、ほこりの厚さは H_i のままなので、足跡は残りません。
  • 高橋君がタイル i を踏んだ場合、ほこりの厚さは \max(0,\; H_i - D_i) になります。これが H_i より真に小さいのは、H_i > 0 かつ D_i > 0 のときに限ります。したがって、H_i = 0 または D_i = 0 ならば踏んでも足跡は残りません。

高橋君は、足跡が残るタイルの数をできるだけ少なくしたいと考えています。高橋君が最適な経路で移動したとき、足跡が残るタイルの数の最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • 入力はすべて整数である。

入力

N
H_1 H_2 \cdots H_N
D_1 D_2 \cdots D_N
  • 1 行目には、タイルの枚数を表す整数 N が与えられる。
  • 2 行目には、各タイルの初期のほこりの厚さを表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。
  • 3 行目には、各タイルを踏んだときのほこりの減少量の上限を表す N 個の整数 D_1, D_2, \ldots, D_N がスペース区切りで与えられる。

出力

高橋君が最適に移動したとき、足跡が残るタイルの数の最小値を 1 行で出力せよ。

入力例 1

5
3 0 5 2 4
1 1 1 1 1

出力例 1

3

入力例 2

8
5 0 3 0 7 0 2 4
2 3 0 1 1 5 1 3

出力例 2

2

入力例 3

15
1 1 0 1 0 1 1 0 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

出力例 3

5

Score : 333 pts

Problem Statement

Takahashi is trying to walk through a long corridor consisting of N tiles arranged in a row. The tiles are numbered from left to right as Tile 1, Tile 2, \ldots, Tile N.

Each tile is covered with dust. Initially, Tile i has dust of thickness H_i. When Takahashi steps on Tile i, the dust thickness on that tile becomes \max(0,\; H_i - D_i), where D_i is a non-negative integer defined for Tile i. The dust thickness on tiles that Takahashi does not step on remains unchanged at the initial thickness H_i.

Takahashi starts at Tile 1, and Tile N is the goal. Takahashi always moves only to the right. Specifically, when he is currently on Tile j, he can choose Tile j+1 or Tile j+2 as his next destination. However, he cannot move beyond Tile N (he can move to Tile j+1 only if j+1 \leq N, and to Tile j+2 only if j+2 \leq N). Takahashi steps on a tile upon arriving at it. He also steps on Tile 1, the starting point. Takahashi ends his movement upon reaching Tile N.

Due to the above movement rules, Tile 1 and Tile N are always stepped on. Also, since Takahashi always moves to the right, he never steps on the same tile more than once.

After Takahashi walks through the corridor, Aoki inspects the corridor and counts the number of tiles with footprints. A footprint is left on Tile i if the dust thickness on Tile i after Takahashi's movement is strictly less than the initial thickness H_i.

  • If Takahashi did not step on Tile i, the dust thickness remains H_i, so no footprint is left.
  • If Takahashi stepped on Tile i, the dust thickness becomes \max(0,\; H_i - D_i). This is strictly less than H_i if and only if H_i > 0 and D_i > 0. Therefore, if H_i = 0 or D_i = 0, no footprint is left even if the tile is stepped on.

Takahashi wants to minimize the number of tiles with footprints. Find the minimum number of tiles with footprints when Takahashi moves along an optimal path.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq H_i \leq 10^9
  • 0 \leq D_i \leq 10^9
  • All input values are integers.

Input

N
H_1 H_2 \cdots H_N
D_1 D_2 \cdots D_N
  • The first line contains an integer N, the number of tiles.
  • The second line contains N integers H_1, H_2, \ldots, H_N separated by spaces, representing the initial dust thickness of each tile.
  • The third line contains N integers D_1, D_2, \ldots, D_N separated by spaces, representing the upper bound of dust reduction when each tile is stepped on.

Output

Print in one line the minimum number of tiles with footprints when Takahashi moves optimally.

Sample Input 1

5
3 0 5 2 4
1 1 1 1 1

Sample Output 1

3

Sample Input 2

8
5 0 3 0 7 0 2 4
2 3 0 1 1 5 1 3

Sample Output 2

2

Sample Input 3

15
1 1 0 1 0 1 1 0 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

5