seoulin1234   1년 전

문제

한때 Lars라고 불렸던 건설 인부가 높이는 1이고 길이가 다양한 벽돌을 많이 가지고 있습니다. 그는 이제 너비가 w이고 높이가 h인 벽을 쌓으려고 합니다. Lars는 부분 집합 합 문제가 NP-난해(NP-hard)라는 것을 알고 있기 때문에, 배치를 최적화하려고 하지 않고 그저 쌓여있는 순서대로 벽돌을 놓고 운에 맡깁니다.

먼저 그는 첫 번째 층에 벽돌을 왼쪽에서 오른쪽으로 놓습니다. 첫 번째 층이 완성되면 두 번째 층으로 이동하여 완성하고, 이런 식으로 계속합니다. 그는 벽돌을 회전시키지 않고 수평으로만 놓습니다. 만약 어느 시점에서 벽돌을 놓을 수 없어 층을 미완성으로 남겨야 한다면, 그는 짜증을 내고 떠나버립니다. 벽을 다 쌓은 후에 벽돌이 남아있는지는 중요하지 않습니다.

어제 Lars는 마지막 층에서 벽을 완성할 수 없다는 것을 깨닫고 정말 짜증이 나서 벽을 허물고 당신에게 도움을 요청했습니다. 오늘 그가 가진 새로운 벽돌 더미로 Lars가 벽을 완성할 수 있는지 말해주시겠습니까?

입력

첫 번째 줄에는 세 개의 정수 h, w, n (1 ≤ h ≤ 100, 1 ≤ w ≤ 100, 1 ≤ n ≤ 10,000)이 주어집니다. 이는 각각 벽의 높이, 벽의 너비, 벽돌의 개수입니다. 두 번째 줄에는 n개의 정수 xi​ (1 ≤ xi​ ≤ 10)가 주어지며, 이는 각 벽돌의 길이입니다.

출력

Lars가 벽을 완성할 수 있다면 YES를, 그렇지 않다면 NO를 출력합니다.

댓글을 작성하려면 로그인해야 합니다.