블로그 언저리인 무언가

문제 : 3321 가장 큰 직사각형 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net 기본적으로 1로 채워진 가장 큰 정사각형을 찾는 문제이지만 열의 순서를 바꿀 수 있으므로 결국 각 행에 대해서 열의 높이를 정렬하여 누적합을 이용하면 행의 길이를 1씩 늘려가면서 최대 넓이를 구할 수 있다. 이를 구현하게 되면 총 행의 개수 N번, 각 행을 정렬하는데 걸리는 시간이 퀵 정렬 사용 시 MlogM이므로 시간 복잡도가 O(NMlogM)이 되는데 시간제한이 0.6초이기 때문에 이를 O(NM)으로 줄여야 한다. 나 같은 경우에는 deque를 사용해 정렬 시간을 ..