102653: [AtCoder]ABC265 D - Iroha and Haiku (New ABC Edition)

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

有一个长度为 $N$ 的数列$A=(A_0,\ldots,A _{N-1})$, 判断有满足以下所有条件的整数 $(x,y,z,w)$ 是否存在 + $0\leq x < y < z < w \le N$ + $A_x+A_{x+1}+\cdots+A_{y-1} = P$ + $A_y+A_{y+1}+\cdots+A_{z-1}= Q$ + $A_z+A_{z+1}+\cdots+A_{w-1}=R$ #### 数据范围: - $3\le N \le 2 \times10^5$ - $1\le A_i \le 10^9$ - $1 \le P,Q,R \le 10^{15}$

Output

分数: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

加入题单

上一题 下一题 算法标签: