시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 3 2 33.333%

문제

크기가 n×m인 행렬 G가 있다. G[i][j]에는 i와 j의 최대공약수가 저장되어져 있다. (1 ≤ i ≤ n, 1 ≤ j ≤ m)

크기가 k인 수열 a1, a2, ..., ak가 주어졌을 때, G에 이 수열이 연속 부분 수열로 등장하는지 안하는지 구하는 프로그램을 작성하시오. 즉, 모든 1 ≤ l ≤ k에 대해서, G[i][j+l-1] = al인 1 ≤ i ≤ n, 1 ≤ j ≤ m-k+1가 존재하는지 아닌지를 구해야 한다.

입력

첫째 줄에 n, m, k (1 ≤ n, m ≤ 1012, 1 ≤ k ≤ 10000)가 주어진다.

둘째 줄에는 a1, a2, ..., ak (1 ≤ ai ≤ 1012)가 주어진다.

출력

G에 주어진 수열이 연속 부분 수열로 등장하면 YES를, 아니면 NO를 출력한다.

예제 입력 1

100 100 5
5 2 1 2 1

예제 출력 1

YES

예제 입력 2

100 8 5
5 2 1 2 1

예제 출력 2

NO

예제 입력 3

100 100 7
1 2 3 4 5 6 7

예제 출력 3

NO

힌트

예제 1의 경우에 G[10][5]부터 G[10][9]까지가 일치한다.

출처