시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 120 41 35 37.634%

문제

대회를 열기 위해서는 굉장히 많은 요소들을 고려해야한다. 그리고 현정이는 어떤 의미로나 좋지 못한 대회를 만드는 것으로 유명하다. 문제 부분에 관해서도, 좋은 대회라고 생각되는 기준을 한 번도 만족해본 적이 없다. 현정이가 만들고 싶은 좋은 대회란 다음 세가지 조건을 모두 만족하는 대회를 말한다.

  1. 모든 참가자가 한 문제 이상을 풀어야 한다.
  2. 모든 문제는 한 명 이상의 참가자에게 풀려야 한다.
  3. 모든 문제를 푼 참가자는 없어야 한다.

이런저런 경험을 겪으며 현정이는 이번에야말로 좋은 대회를 만들어내기 위해 모든 것을 바쳤다. 하지만 너무 많은 것을 바쳤는지 대회가 끝나기 전에 쓰러져버렸다. 눈을 뜬 현정이는 가장 먼저 대회 결과를 보고 이번 대회가 좋은 대회였는지를 알고싶어했다.

서둘러 대회 홈페이지에 접속한 현정이는 대회 결과를 나타내는 스코어보드를 찾아냈다. 하지만 현정이의 노트북은 모니터의 오른쪽 상단이 삼각형 모양으로 깨져있어 전체 스코어보드의 모습을 보지 못했다.

스코어보드는 더 많은 문제를 맞춘 참가자가 더 순위가 높고, 1등이 가장 위에 위치해 순위대로 정렬되어있는 형태다. 현정이의 모니터는 ◥ 모양으로 깨져있기 때문에 볼 수 있는 스코어보드의 형태는 아래 규칙을 모두 만족한다.

  • i 등 참가자의 x 번 문제 결과를 볼 수 있다면 (i+1) ~ N등 참가자의 x번 문제 결과 역시 볼 수 있다.
  • i 등 참가자의 x 번 문제 결과를 볼 수 없다면, 1 ~ (i-1) 등 참가자의 x번 문제 결과 역시 볼 수 없다.
  • i 등 참가자의 x 번 문제 결과를 볼 수 있다면, 1 ~ x 번 문제 결과 역시 볼 수 있다. 
  • i 등 참가자의 x 번 문제 결과를 볼 수 없다면, x ~ M 번 문제 결과 역시 볼 수 없다. 

현정이가 알 수 있는 것은 각 참가자들이 몇 문제를 풀었는지와 어떤 문제를 풀었는지에 대한 부분적인 정보이다. 현정이는 머릿속에서 행복회로를 가동하기 시작했다. 모니터가 깨져 볼 수 없는 부분을 자신이 원하는대로 채워 이 대회가 좋은대회였을 것이라고 믿는 것이다. 물론 각 참가자들이 맞춘 문제수와 볼 수 있는 결과들이 변경될 수는 없다. 깨어진 모니터에 보이는 스코어보드 정보가 주어졌을 때, 이 대회가 좋은 대회가 될 수 있는지를 알아보자.

입력

첫 줄에 이번 대회의 참가자의 수 N(1 ≤ N ≤ 100)과 문제의 수 M(1 ≤ M ≤ 10)이 주어진다. 다음 N 개의 줄에는 1등부터 N 등까지, i 등 참가자의 맞춘 문제 수 Ki (0 ≤ Ki ≤ M)와 해당 참가자의 1 ~ M번 문제에 대한 결과가 M 개가 주어진다. 결과는 맞았다면 1, 틀렸다면 0, 찢어져 결과를 알 수 없다면 -1로 주어진다.

출력

좋은대회가 될 수 있다면 “YES”, 아니라면  “NO”를 출력한다.

예제 입력 1

4 5
4 1 1 -1 -1 -1
3 1 0 -1 -1 -1
2 1 0 1 0 -1
1 1 0 0 0 -1

예제 출력 1

YES

예제 입력 2

5 7
4 1 1 1 -1 -1 -1 -1
3 1 1 1 0 -1 -1 -1
3 1 0 1 0 -1 -1 -1
2 1 0 0 0 1 -1 -1
1 0 0 1 0 0 -1 -1

예제 출력 2

NO

힌트

아래는 1번 예제가 좋은 대회가 될 수 있는 다양한 결과 중 하나이다.

1 1 0 1 1
1 0 1 0 1
1 0 1 0 0
1 0 0 0 0

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2017 A번

  • 문제를 만든 사람: Acka
  • 데이터를 추가한 사람: cubelover
  • 문제의 오타를 찾은 사람: skdi3658

채점

  • 예제는 채점하지 않는다.