시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 195 | 68 | 64 | 38.554% |
N*M 격자에 서로 다른 수가 하나씩 들어가 있다. XOR 그룹이라는 것을 정의를 하여 합을 최대로 하려한다. XOR 그룹이란 위, 아래, 오른쪽, 왼쪽으로 인접한 칸에 수가 있다면, 그 칸과 연결되어 그 수를 모두 XOR한 값을 가지는 그룹이 된다. 만약, 중간에 수가 빠져있으면, 연결이 되지 않으므로, 한 격자판에 여러 XOR 그룹이 있을 수 있다.
이제 격자판에서 작은 수부터 제거해 나갈 것이다. 하나를 지울 때 마다 XOR 그룹이 변하는데, XOR그룹의 값의 합의 최대가 될 때, 그 값을 구하여라.
첫째 줄에 n, m이 주어진다.(1 ≤ n, m ≤ 1,000)
다음 n줄에는 격자의 i번째 줄의 수 m개가 주어진다. 수는 1,000,000보다 크지 않은 음이 아닌 정수이다.
XOR 그룹의 값의 합이 최대가 되는 값을 구하여라
3 4 9 1 15 16 3 4 10 6 2 5 7 11
42