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