| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 179 | 100 | 97 | 60.625% |
동우의 핸들 kidw0124에서 알 수 있듯이 동우의 생일은 정확히 일주일 뒤인 1월 24일이다.
세진이는 MatKor Cup을 부활시키기 위해 동우를 설득하는 중이다. 마침 동우의 생일을 알게 된 세진이는 이건 기회라고 생각하며 동우의 선물을 준비했다. 세진이는 두 변의 길이가 각각 $A$, $B$인 직사각형 선물 $N$개를 하나의 큰 직사각형 모양 상자에 담으려 한다.
각 선물은 그대로 두거나 $90^\circ$ 회전시켜 배치할 수 있으며, 각 선물의 회전 여부는 독립적으로 결정할 수 있다. 선물들은 서로 겹치지 않게 각 변이 수직 혹은 평행하게 평면 위에 배치한다.
모든 선물은 서로 연결되어 있어야 한다. 두 선물이 변이나 꼭짓점에서 한 점이라도 맞닿아 있으면 서로 연결되어 있다고 하며, 이 연결 관계는 전이적으로 확장된다. 즉, 선물 $X$와 $Y$가 연결되어 있고 $Y$와 $Z$가 연결되어 있으면 $X$와 $Z$도 연결되어 있다.
상자는 배치된 선물들을 모두 포함하는 직사각형 모양이어야 하며, 상자 역시 가로 변과 세로 변이 선물들의 가로, 세로 방향에 평행해야 한다. 상자는 조건을 만족하는 직사각형 중 최소의 직사각형으로, 선물 배치에 외접한다.
동우에게 최대한 잘 보이고 싶은 세진이는 선물들을 적절히 배치하여 상자의 면적이 최대가 되도록 하려 한다. 세진이가 준비할 수 있는 상자의 최대 면적을 구해보자.
첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 100\, 000)$가 주어진다.
두 번째 줄부터 $T$줄에 걸쳐 각 테스트 케이스 별로 한 줄씩 선물의 두 변의 길이를 나타내는 정수 $A,B(1\le A,B\le 1\, 000)$와 선물의 개수 $N(1\le N\le 10^6)$이 공백으로 구분되어 주어진다.
각 테스트 케이스 별로 한 줄씩 정답을 출력한다.
4 1 1 1 1 3 1 1 3 2 1000 1000 1000000
1 3 16 1000000000000000000
첫 번째와 두 번째 테스트 케이스는 선물이 한 개이므로 상자의 모양이 선물 하나와 일치해야 한다.
세 번째 테스트 케이스는 다음과 같이 배치하면 $4\times 4$로 배치할 수 있어, 최대 면적은 $16$이다.
네 번째 테스트 케이스는 $10^9\times 10^9$으로 배치할 수 있어, 최대 면적은 $10^{18}$이다.
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 2 B번