Rest Stops

• 그리디하게 풀리는 문제.
• tastiness 가 가장 높은 지점에서 가능한 오랫동안 먹는것이 최적이다. x[i]<x[j] 이고, c[i]<c[j] 라면 i번째 stop에서 쉬지 않고, j번째 stop에서 쉬는 것이 최적이 된다.
• 그러면 최적해를 찾는 것은, c[i]가 가장 큰곳에서 x[i]*(rF-rB)만큼 머무르고, 이제 x[j]>x[i]인 지점들 중 c[j]가 최대가 되는 j를 찾아서 다시 (x[j]-x[i])*(rF-rB)만큼 머무르고,.. 다시 x[j]보다 더 멀리있는 지점들중에서 최대를 찾고 하는 것을 반복하면 된다.
• 처음에 푼 방법은, c가 큰 순서대로 정렬하고, 이터레이션을 하면서 x가 이전에 머물렀던 지점보다 더 뒤에 있는 경우에만 값을 더하고 이전에 머물렀던 지점을 갱신하는 식으로 처리하는 것이다. 정렬에 O(nlogn), 이터레이션에 O(n)이 걸려서 총 O(nlogn)에 해결된다
• 하지만 다른 사람의 답안을 보고, 정렬조차도 필요 없다는 것을 깨달았다. x가 증가하는 순서대로 주어지는 지점들에 대해서 c값이 내림차순이 되는 지점들만 남겨놓고, 이것들을 대상으로 이터레이션을 하는 것으로도 최적해를 구할수 있다. c값이 내림차순이 되는 지점들만 뽑는 것은 x가 증가하는 순서대로 읽으면서 처리해도 monotone stack을 이용해서 O(n)에 가능하긴 하지만, 뒤에서부터 x가 감소하는 순서대로 읽으면 더 간단하게 O(n)에 구할수 있다. 총 시간복잡도도 O(n)이 된다.

"""Solution code for "BOJ 15748. Rest Stops".

- Problem link: https://www.acmicpc.net/problem/15748
- Solution link: http://www.teferi.net/ps/problems/boj/15748

Tags: [Greedy]
"""

import sys
import operator


def main():
    # pylint: disable=unused-variable
    L, N, rF, rB = [int(x) for x in sys.stdin.readline().split()]
    stops = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    answer = 0
    prev_pos = 0
    for pos, tastiness in sorted(stops,
                                 key=operator.itemgetter(1),
                                 reverse=True):
        if pos > prev_pos:
            answer += tastiness * (rF - rB) * (pos - prev_pos)
            prev_pos = pos

    print(answer)


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 15748. Rest Stops".

- Problem link: https://www.acmicpc.net/problem/15748
- Solution link: http://www.teferi.net/ps/problems/boj/15748

Tags: [Greedy]
"""

import itertools
import sys

INF = float('inf')


def main():
    # pylint: disable=unused-variable
    L, N, rF, rB = [int(x) for x in sys.stdin.readline().split()]
    stops = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    stops_to_rest = []
    max_tastiness = 0
    for pos, tastiness in reversed(stops):
        if tastiness > max_tastiness:
            max_tastiness = tastiness
            stops_to_rest.append((pos, tastiness))
    stops_to_rest.append((0, INF))

    speed_diff = rF - rB
    answer = sum(s2[1] * (s2[0] - s1[0]) * speed_diff
                 for s1, s2 in itertools.pairwise(reversed(stops_to_rest)))
    print(answer)


if __name__ == '__main__':
    main()