레이팅 미적용농부 존의 소 \(N\)마리는 편의상 \(1 \ldots N\)으로 번호가 매겨져 있으며 일렬로 서 있다(\(1\le N\le 5\cdot 10^4\)). \(i\)번째 소에게는 \(1 \ldots K\) 범위의 품종 식별자 \(b_i\)가 있으며, \(1\le K\le 50\)이다. 소들은 소 \(1\)에서 소 \(N\)까지 메시지를 가장 잘 전달하는 방법을 알아내기 위해 당신의 도움이 필요하다.
소 \(i\)에서 소 \(j\)로 메시지를 전달하는 데는 \(|i-j|\)의 시간이 걸린다. 하지만 모든 품종이 서로 소통하려 하는 것은 아니며, 이는 \(K \times K\) 행렬 \(S\)로 주어진다. \(S_{ij} = 1\)이면 품종 \(i\)의 소가 품종 \(j\)의 소에게 메시지를 전달할 의향이 있다는 뜻이고, \(0\)이면 그렇지 않다는 뜻이다. \(S_{ij}=S_{ji}\)가 반드시 성립하는 것은 아니며, 품종 \(i\)의 소들이 서로 소통하려 하지 않는다면 \(S_{ii} = 0\)일 수도 있다.
메시지를 전달하는 데 필요한 최소 시간을 구하시오.
문제 제공: Dhruv Rohatgi
배점
- 테스트 케이스 1-5는 \(N\le 1000\)을 만족한다.
- 테스트 케이스 6-13에는 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 \(N\)과 \(K\)가 주어진다.
다음 줄에 공백으로 구분된 \(N\)개의 정수 \(b_1,b_2,\ldots,b_N\)이 주어진다.
다음 \(K\)개의 줄에는 행렬 \(S\)가 주어진다. 각 줄은 \(K\)개의 비트로 이루어진 문자열이며, \(S_{ij}\)는 위에서 \(i\)번째 문자열의 \(j\)번째 비트이다.
필요한 최소 시간을 정수 하나로 출력한다. 소 \(1\)에서 소 \(N\)까지 메시지를 전달하는 것이 불가능하다면 \(-1\)을 출력한다.
5 4
1 4 2 3 4
1010
0001
0110
01006The optimal sequence of transmissions is \(1\to 4\to 3\to 5\). The total amount of
time is \(|1-4|+|4-3|+|3-5|=6\).