/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
周期 N をもつ無限数列 A=(A _ 1,A _ 2,A _ 3,\dotsc) の先頭 N 項 A _ 1,A _ 2,\dotsc,A _ N が与えられます。
この数列の空でない連続する部分列のうち、和が S となるものが存在するか判定してください。
ただし、無限数列 A が周期 N をもつとは、i\gt N を満たすすべての整数 i に対して A _ i=A _ {i-N} が成り立つことをいいます。
制約
- 1\leq N\leq2\times10 ^ 5
- 1\leq A _ i\leq 10 ^ 9
- 1\leq S\leq 10 ^ {18}
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N S A _ 1 A _ 2 \dotsc A _ N
出力
A の連続する部分列 (A _ l,A _ {l+1},\dotsc,A _ r) であって、A _ l+A _ {l+1}+\dotsb+A _ r=S となるものが存在するならば Yes を、そうでないならば No を出力せよ。
入力例 1
3 42 3 8 4
出力例 1
Yes
数列 A は (3,8,4,3,8,4,3,8,4,\dotsc) のようになります。
A の部分列 (A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7,A _ 8,A _ 9)=(8,4,3,8,4,3,8,4) について 8+4+3+8+4+3+8+4=42 が成り立つので、Yes を出力してください。
入力例 2
3 1 3 8 4
出力例 2
No
A の要素はすべて 3 以上なので、A の空でない連続する部分列の総和は 3 以上です。
よって、総和が 1 となるような部分列は存在しないため、No を出力してください。
入力例 3
20 83298426 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772
出力例 3
Yes
入力例 4
20 85415869 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772
出力例 4
No
Score : 400 points
Problem Statement
You are given the first N terms A _ 1,A _ 2,\dotsc,A _ N of an infinite sequence A=(A _ 1,A _ 2,A _ 3,\dotsc) that has period N.
Determine if there exists a non-empty contiguous subsequence of this infinite sequence whose sum is S.
Here, an infinite sequence A has period N when A _ i=A _ {i-N} for every integer i>N.
Constraints
- 1\leq N\leq2\times10 ^ 5
- 1\leq A _ i\leq 10 ^ 9
- 1\leq S\leq 10 ^ {18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S A _ 1 A _ 2 \dotsc A _ N
Output
If there exists a contiguous subsequence (A _ l,A _ {l+1},\dotsc,A _ r) of A for which A _ l+A _ {l+1}+\dotsb+A _ r=S, print Yes. Otherwise, print No.
Sample Input 1
3 42 3 8 4
Sample Output 1
Yes
The sequence A is (3,8,4,3,8,4,3,8,4,\dotsc).
For the subsequence (A _ 2,A _ 3,A _ 4,A _ 5,A _ 6,A _ 7,A _ 8,A _ 9)=(8,4,3,8,4,3,8,4), we have 8+4+3+8+4+3+8+4=42, so print Yes.
Sample Input 2
3 1 3 8 4
Sample Output 2
No
All elements of A are at least 3, so the sum of any non-empty contiguous subsequence is at least 3.
Thus, there is no subsequence with sum 1, so print No.
Sample Input 3
20 83298426 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772
Sample Output 3
Yes
Sample Input 4
20 85415869 748 169 586 329 972 529 432 519 408 587 138 249 656 114 632 299 984 755 404 772
Sample Output 4
No