请求修复latex
查看原帖
请求修复latex
727008
lwx20211103楼主2023/1/27 17:40

[ABC265D] Iroha and Haiku (New ABC Edition)

题面翻译

题意：

有一个长度为NN的数列A=(A0,...,AN−1)A=(A_0,...,A _{N-1}),

判断有满足以下所有条件的整数(x,y,z,w)(x,y,z,w)是否存在

  • 0≥x<y<z<w≤N\color{red}0\geq x < y < z < w \le N(error) 0≤x<y<z<w≤N0 \leq x < y < z < w \leq N(correct)
  • Ax+Ax+1+...+Ay−1=PA_x+A_{x+1}+...+A_{y-1} = P
  • Ay+Ay+1+...+Az−1=QA_y+A_{y+1}+...+A_{z-1}= Q
  • Az+Az+1+...+Aw−1=RA_z+A_{z+1}+...+A_{w-1}=R

数据范围：

  • 3≤N≤2×1053\le N \le 2 \times10^5
  • 1≤Ai≤1091\le A_i \le 10^9
  • 1≤P,Q,R≤10151 \le P,Q,R \le 10^{15}

题目描述

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

  • 0 ≤ x < y < z < w ≤ N0\ \leq\ x\ <\ y\ <\ z\ <\ w\ \leq\ N
  • Ax + Ax+1 + … + Ay−1 = PA_x\ +\ A_{x+1}\ +\ \ldots\ +\ A_{y-1}\ =\ P
  • Ay + Ay+1 + … + Az−1 = QA_y\ +\ A_{y+1}\ +\ \ldots\ +\ A_{z-1}\ =\ Q
  • Az + Az+1 + … + Aw−1 = RA_z\ +\ A_{z+1}\ +\ \ldots\ +\ A_{w-1}\ =\ R

输入格式

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

NN PP QQ RR A0A_0 A1A_1 …\ldots AN−1A_{N-1}

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

Yes

样例 #2

样例输入 #2

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

样例输出 #2

No

样例 #3

样例输入 #3

7 1 1 1
1 1 1 1 1 1 1

样例输出 #3

Yes

提示

制約

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

Sample Explanation 1

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

源代码：

# [ABC265D] Iroha and Haiku (New ABC Edition)

## 题面翻译

题意：

有一个长度为$N$的数列$A=(A_0,...,A
_{N-1})$,

判断有满足以下所有条件的整数$(x,y,z,w)$是否存在

+ $\color{red}0\geq x < y < z < w \le N$(error)
$0 \leq x < y < z < w \leq N$(correct)
+ $A_x+A_{x+1}+...+A_{y-1} = P$
+ $A_y+A_{y+1}+...+A_{z-1}= Q$
+ $A_z+A_{z+1}+...+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}$

## 题目描述

[problemUrl]: https://atcoder.jp/contests/abc265/tasks/abc265_d

長さ $ 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 $

## 输入格式

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

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

## 输出格式

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

## 样例 #1

### 样例输入 #1

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


### 样例输出 #1

Yes


## 样例 #2

### 样例输入 #2

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


### 样例输出 #2

No


## 样例 #3

### 样例输入 #3

7 1 1 1 1 1 1 1 1 1 1


### 样例输出 #3

Yes


## 提示

### 制約

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

### Sample Explanation 1

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

（管理员在休假）

2023/1/27 17:40