← 返回题目列表

AtCoder · abc255_e

H. 幸运数字

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个序列 N-1 整数 S = (S_1, S_2, \ldots, S_{N-1}),和 M 不同的整数 X_1, X_2, \ldots, X_M,称为 幸运数字.

一系列 N 整数 A = (A_1, A_2, \ldots, A_N) 满足以下条件称为 好的序列.

A_i + A_{i+1} = S_i 对于每个都成立 i = 1, 2, \ldots, N-1.

找出良好序列中幸运数字的最大可能数量 A,即最大可能的整数个数 i 之间 1 和 N 这样 A_i \in \lbrace X_1, X_2, \ldots, X_M \rbrace.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 10
  • -10^9 \leq S_i \leq 10^9
  • -10^9 \leq X_i \leq 10^9
  • X_1 \lt X_2 \lt \cdots \lt X_M
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
S_1 S_2 \ldots S_{N-1}
X_1 X_2 \ldots X_M

输出

以良好的顺序打印幸运数字的最大可能数量 A.


示例输入 1

9 2
2 3 3 4 -4 -7 -4 -1
-1 5

示例输出 1

4

一个好的序列 A = (3, -1, 4, -1, 5, -9, 2, -6, 5) 包含四个幸运数字项: A_2, A_4, A_5, A_9,这是最大可能计数。


示例输入 2

20 10
-183260318 206417795 409343217 238245886 138964265 -415224774 -499400499 -313180261 283784093 498751662 668946791 965735441 382033304 177367159 31017484 27914238 757966050 878978971 73210901
-470019195 -379631053 -287722161 -231146414 -84796739 328710269 355719851 416979387 431167199 498905398

示例输出 2

8