Codeforces Round #795 (Div. 2) D. Max GEQ Sum

Problem - D - Codeforces

이것도 풀 수 있었는데 못 풀었다.

풀이는 맞았는데 구현에서 애먹다가 펑! 20분 정도만 더 줬으면 AC 받을 문제였다.

세그먼트 트리로 그냥 풀면 되는데

배열에서 자기 자신보다 큰 가장 가까운 원소 찾는 것을

그냥 스택을 써서 구현하면 되는데 멀티 맵을 써서 구현하다가 시간 다 까먹었다.

17298번: 오큰수

이문제를 풀었으면서 왜 이상하게 구현을 했는지 모르겠다.

일단 이번 D문제의 풀이는 간단하다.

세그먼트 트리는 2개가 필요하고 각 원소는 특정 원소와 각 원소 까지의 부분합이 저장되어 있다.

여기서 특정 원소는 합에서 제외한다. (스위핑 하면서 세그먼트 트리를 관리해야 한다.)

그리고 최댓값이 저장되어 있다.

특정 원소는 주어진 배열을 스위핑 하면서 관찰하고 있는 원소다.

스위핑 하면서 (특정 원소의 위치-1)부터 (왼큰수의 위치+1)까지의 (특정 원소의 위치-1)을 포함하는 각 각의 연속 합의 최댓값이 0보다 크거나 (특정 원소의 위치+1)부터 (오큰수의 위치-1)까지 (특정 원소의 위치+1)을 포함하는 각 각의 연속 합의 최댓값이 0보다 크다면 답은 NO이고 이러한 조건을 만족하는 특정 원소가 존재하지 않다면 답은 YES이다.