아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

체육 대회

시간 제한1초메모리 제한1024 MB

요약
팀 A가 15명의 병사를 세 종목에 5명씩 배치해, B, C, D가 어떻게 배치하든 반드시 우승할 수 있는지 판정한다.
난이도

보통10점 중 6점

유형
그리디, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

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

겨루는 종목은 총 33가지로, 각 팀의 병사들은 세 가지 종목에 대해 각각 실력 a_ij,b_ij,c_ij,d_ija\_{ij}, b\_{ij}, c\_{ij}, d\_{ij}를 가진다. 이때, a_ija\_{ij}는 팀 AA의 ii번째 병사의 jj번째 종목에 대한 실력이다.

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

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

입력

첫 번째 줄부터 세 번째 줄까지, jj번째 줄에 팀 AA의 ii번째 병사의 종목 jj에 대한 실력을 나타내는 정수 a_ija\_{ij}가 공백으로 구분되어 1515개씩 주어진다. (1≤a_ij≤15)(1\leq a\_{ij}\leq 15)

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

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

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

출력

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

예제2

  1. 예제 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
    
    예상 출력
    YES
    
  2. 예제 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
    
    예상 출력
    NO