D - Iroha and Haiku (New ABC Edition) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の数列 A=(A_0,\ldots,A_{N-1}) があります。
次の条件を全て満たす整数の組 (x,y,z,w) が存在するか判定してください。

  • 0 \leq x < y < z < w \leq N
  • A_x + A_{x+1} + \ldots + A_{y-1} = P
  • A_y + A_{y+1} + \ldots + A_{z-1} = Q
  • A_z + A_{z+1} + \ldots + A_{w-1} = R

制約

  • 3 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq P,Q,R \leq 10^{15}
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N P Q R
A_0 A_1 \ldots A_{N-1}

出力

条件を満たす組が存在するなら Yes、存在しないなら No を出力せよ。

入力例 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

出力例 1

Yes

(x,y,z,w)=(1,3,6,8) が条件を満たします。

入力例 2

9 100 101 100
31 41 59 26 53 58 97 93 23

出力例 2

No

入力例 3

7 1 1 1
1 1 1 1 1 1 1

出力例 3

Yes

Score : 400 points

Problem Statement

There is a sequence A=(A_0,\ldots,A_{N-1}) of length N.
Determine if there exists a tuple of integers (x,y,z,w) that satisfies all of the following conditions:

  • 0 \leq x < y < z < w \leq N
  • A_x + A_{x+1} + \ldots + A_{y-1} = P
  • A_y + A_{y+1} + \ldots + A_{z-1} = Q
  • A_z + A_{z+1} + \ldots + A_{w-1} = R

Constraints

  • 3 \leq N \leq 2\times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq P,Q,R \leq 10^{15}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N P Q R
A_0 A_1 \ldots A_{N-1}

Output

If there exists a tuple that satisfies the conditions, print Yes; otherwise, print No.

Sample Input 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

Sample Output 1

Yes

(x,y,z,w)=(1,3,6,8) satisfies the conditions.

Sample Input 2

9 100 101 100
31 41 59 26 53 58 97 93 23

Sample Output 2

No

Sample Input 3

7 1 1 1
1 1 1 1 1 1 1

Sample Output 3

Yes