농작물 수확

씨앗들을 좌표의 오름차순으로 정렬하자. 정렬된 $j$번 씨앗이 원래 $p_j$번 씨앗이었다고 하자. 즉, $p_j$는 그 씨앗을 수확할 수 있는 날짜이다.

수확하기로 선택한 씨앗들만 좌표 순서대로 보자. 이들의 날짜는 반드시 어떤 한 지점을 기준으로 엄격히 감소하다가 엄격히 증가하는 형태여야 한다.

선택한 씨앗 중 가장 이른 날에 수확하는 씨앗을 중심 씨앗이라 하자. 중심 씨앗보다 왼쪽에 있는 선택된 씨앗들을 좌표가 증가하는 순서로 보면 날짜는 엄격히 감소해야 한다. 그렇지 않으면 더 왼쪽에 있으면서 더 이른 날에 수확하는 씨앗으로 이동할 때, 그 사이에 있는 아직 수확되지 않은 선택된 씨앗을 밟게 된다.

같은 이유로 중심 씨앗보다 오른쪽에 있는 선택된 씨앗들의 날짜는 좌표가 증가하는 순서로 엄격히 증가해야 한다.

반대로 날짜가 엄격히 감소하다가 엄격히 증가하는 형태인 씨앗들을 선택하면 모두 수확할 수 있다. 중심 씨앗을 처음 수확한 뒤, 날짜 순서대로 볼 때 다음 씨앗은 이미 수확한 구간의 왼쪽 바깥 또는 오른쪽 바깥에 있는 가장 가까운 선택된 씨앗이다. 따라서 이동 경로에 아직 수확되지 않은 선택된 씨앗이 없다.

결국 문제는 좌표 순서로 놓인 수열

$$p_1,p_2,\cdots,p_N$$

에서 가치 $w_{p_j}$를 가진 원소들을 골라, 날짜가 엄격히 감소하다가 엄격히 증가하는 부분수열의 가치 합을 최대화하는 문제가 된다.

$L_j$를 $j$번 위치를 마지막 원소로 하는 엄격히 감소하는 부분수열의 최대 가치 합이라 하자. 그러면

$$L_j=w_{p_j}+\max_{k<j,\ p_k>p_j}L_k$$

이다.

$R_j$를 $j$번 위치를 첫 원소로 하는 엄격히 증가하는 부분수열의 최대 가치 합이라 하자. 그러면

$$R_j=w_{p_j}+\max_{k>j,\ p_k>p_j}R_k$$

이다.

두 식 모두 현재 날짜 $p_j$보다 큰 날짜 구간의 최댓값이 필요하다. 날짜는 $1$부터 $N$까지의 서로 다른 정수이므로 세그먼트 트리를 날짜에 대해 만들면 된다.

$L_j$는 왼쪽에서 오른쪽으로 계산한다. 세그먼트 트리에서 구간 $(p_j,N]$의 최댓값을 구한 뒤 $p_j$ 위치를 로 갱신한다.

$R_j$는 오른쪽에서 왼쪽으로 같은 방식으로 계산한다.

$j$번 씨앗을 중심으로 하는 최적의 답은

$$L_j+R_j-w_{p_j}$$

이다. 중심 씨앗의 가치가 두 번 더해졌으므로 한 번 빼야 한다.

모든 $j$에 대한 최댓값이 정답이다. 좌표 정렬과 세그먼트 트리 연산이 필요하므로 시간 복잡도는 $O(N\log N)$이고, 메모리 복잡도는 $O(N)$이다.

모든 가치는 양수이므로 답은 모든 씨앗 가치의 합을 넘지 않는다. 따라서

$$\text{answer}\leq N\cdot10^9\leq2\cdot10^{14}$$

이고 항상 부호 있는 $64$비트 정수 범위에 들어간다.

Solution written by GPT5.6