| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 206 | 113 | 92 | 61.745% |
바다에 $N$마리의 돌고래가 살고 있다. 각 돌고래에는 1ドル$번부터 $N$번까지 번호가 붙어 있고, 각 돌고래는 자신만의 서식지에 살고 있다. 돌고래들은 가끔씩 자신의 서식지에서 묘기를 펼친다.
사진가 승진이는 돌고래들의 묘기를 촬영하기 위해 바다에 왔다. 승진에게 주어진 시간은 총 $K$시간이다. 시각 $t$ $(1\le t\le K)$에 승진이는 다음과 같은 세 가지 행동 중 하나를 할 수 있다.
돌고래들이 묘기를 펼치는 시각에 대한 $N\times K$ 크기의 행렬 $M$이 있다. 만약 $M_{i,j}=1$이라면, $i$번 돌고래는 시각 $j$에 묘기를 펼친다. 만약 $M_{i,j}=0$이라면, $i$번 돌고래는 시각 $j$에 묘기를 펼치지 않는다.
승진이는 최대한 많은 수의 돌고래의 묘기를 촬영하고자 한다. 승진이가 최적으로 행동할 때, 묘기를 촬영할 수 있는 서로 다른 돌고래가 최대 몇 마리인지 구해 보자.
첫 번째 줄에 돌고래의 수 $N$과 승진에게 주어진 시간 $K$가 공백을 사이에 두고 주어진다.
두 번째 줄부터 $N+1$번째 줄까지, $i+1$번째 줄에는 $K$개의 정수 $M_{i,1},M_{i,2},\cdots ,M_{i,K}$가 공백을 사이에 두고 주어진다.
묘기를 촬영할 수 있는 서로 다른 돌고래가 최대 몇 마리인지 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $N \le 6,ドル $K \le 12$ |
| 2 | 11 | $N \le 15,ドル $K \le 30$ |
| 3 | 36 | $N < K,ドル $M_{i, j} = 0$ (1ドル \le i \le N,ドル 1ドル \le j \le \pmb{N}$) |
| 4 | 46 | 추가 제약 조건 없음. |
3 5 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0
2
예제 1에서, 다음과 같이 행동하면 돌고래 2ドル$마리의 묘기를 촬영할 수 있다.
이보다 더 많은 수의 돌고래의 묘기를 촬영하는 방법은 존재하지 않는다.
6 10 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
4
3 3 1 0 0 1 0 0 1 0 0
0
3 4 0 0 0 1 0 0 0 1 0 0 0 1
1