시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB24131047.619%

문제

설날을 기념하여 체육대회가 시작된다! $60$명의 병사가 참여하는 이 대회는 팀 $A, B, C, D$에 각각 $15$명씩, 총 네 팀으로 나누어서 진행된다.

겨루는 종목은 총 $3$가지로, 각 팀의 병사들은 세 가지 종목에 대해 각각 실력 $a_{ij}, b_{ij}, c_{ij}, d_{ij}$를 가진다. 이때, $a_{ij}$는 팀 $A$의 $i$번째 병사의 $j$번째 종목에 대한 실력이다.

각 종목은 네 팀의 대항전으로, $5$ vs $5$ vs $5$ vs $5$ 형태로 진행되며 각 병사는 세 종목의 경기 중 한 경기에만 참여할 수 있다. 각 종목에 나온 $5$명의 병사들의 실력의 합이 가장 큰 팀이 해당 종목에서 승리하게 되며, 실력의 합이 가장 큰 팀이 두 팀 이상이라면 무승부 처리된다. 세 종목에 대한 경기가 모두 끝난 뒤, 두 종목 이상에서 승리를 차지한 팀이 우승팀이 된다.

팀 $A$를 열렬히 응원하던 병사는 문득 다른 세 팀이 병사를 어떻게 배치하든 팀 $A$가 우승팀이 될 수 있는 최적의 병사 배치가 있는지 궁금해졌다. 다른 세 팀이 각 종목에 병사를 배치하는 모든 경우의 수에 대해 팀 $A$가 우승팀이 될 수 있는 최적의 병사 배치 여부를 구해주자.

입력

첫 번째 줄부터 세 번째 줄까지, $j$번째 줄에 팀 $A$의 $i$번째 병사의 종목 $j$에 대한 실력을 나타내는 정수 $a_{ij}$가 공백으로 구분되어 $15$개씩 주어진다. $(1\leq a_{ij}\leq 15)$

네 번째 줄부터 여섯 번째 줄까지, $j+3$번째 줄에 팀 $B$의 $i$번째 병사의 종목 $j$에 대한 실력을 나타내는 정수 $b_{ij}$가 공백으로 구분되어 $15$개씩 주어진다. $(1\leq b_{ij}\leq 15)$

일곱 번째 줄부터 아홉 번째 줄까지, $j+6$번째 줄에 팀 $C$의 $i$번째 병사의 종목 $j$에 대한 실력을 나타내는 정수 $c_{ij}$가 공백으로 구분되어 $15$개씩 주어진다. $(1\leq c_{ij}\leq 15)$

열 번째 줄부터 열두 번째 줄까지, $j+9$번째 줄에 팀 $D$의 $i$번째 병사의 종목 $j$에 대한 실력을 나타내는 정수 $d_{ij}$가 공백으로 구분되어 $15$개씩 주어진다. $(1\leq d_{ij}\leq 15)$

출력

다른 세 개의 팀이 병사들을 어떻게 배치하더라도 팀 $A$가 반드시 우승할 수 있는 최적의 경우의 수가 있다면 YES, 없다면 NO를 출력한다.

예제 입력 1

15 15 15 15 15 12 6 3 9 13 9 13 15 8 7
11 9 1 12 9 15 15 15 15 15 6 7 14 2 15
13 12 4 15 3 10 8 5 7 8 15 15 15 15 15
7 6 14 6 6 4 9 11 6 14 6 13 9 15 11
6 15 8 11 15 15 13 7 11 14 2 15 1 9 13
10 13 7 7 13 4 10 9 6 7 15 8 6 1 6
7 11 8 9 15 1 8 11 1 7 12 14 7 2 13
12 6 1 6 8 11 9 12 12 12 4 14 12 10 15
7 6 10 7 14 10 6 12 10 12 6 2 8 6 11
13 11 12 7 8 9 6 13 7 8 9 14 12 10 8
7 13 12 11 8 10 4 10 9 12 12 12 6 15 14
7 13 15 3 15 7 8 14 13 11 6 7 15 14 8

예제 출력 1

YES

종목 $1$에 $1$번부터 $5$번 병사까지, 종목 $2$에 $6$번부터 $10$번 병사까지, 종목 $3$에 $11$번부터 $15$번 병사까지 묶으면 팀 $B$, 팀 $C$, 팀 $D$에서 어떤 방식으로 종목당 병사를 구성해도 팀 $A$가 종목 $1, 2, 3$ 세 경기 모두 승리하여 우승팀이 된다.

예제 입력 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

예제 출력 2

NO

모든 경기가 무승부가 되며, 우승팀은 존재하지 않는다.

출처

Contest > 보라매컵 > 제1회 보라매컵 본선 F번