#5484 정원
https://www.acmicpc.net/problem/5484 문제설명은 힌트로 대체한다. 우리는 겹치지 않는 두개의 직사각형을 골라야 한다. 각각의 직사각형 내부에, 장미가 k개 있으면 된다! 요즘 ps에 대한 자신감이 하락하고 있었는데, 어떻게 갑자기 플레1을 내힘으로 풀었다! 어려운 문제 푸는게 확실히 구현력, 사고력에 도움이 되는듯. 정해는 모르겠는데 나는 $O(logN*N^2)$에 해결했다. 어떻게 풀까? prefixsum+binary_search+dp로 해결 가능하다. 우리가 1번 직사각형을 선택한다고 해보자. 그럼 전체 꽃밭에 있어서, 1,2,3,4,5로 나누어진다. (각각 겹치는 부분이 있다.) 1. 2차원 prefix_sum으로 우리가 원하는 범위에 꽃이 몇개있는지를 O(1)에 가져오..