====== Batch Scheduling ======

===== 풀이 =====
  * 지문이 영어인데다가 잘 안읽힌다..
  * 배치별로 나누면 같은 배치안에서는 똑같은 O값을 갖게 된다. 따라서 i...j 를 배치로 묶으면 그 배치안의 잡들의 코스트의 합은 그냥 Oi*(Fi+...+Fj) 가 된다.
  * 그러면 이제 대충 DP 형태로 점화식을 세울수 있을것 같은 느낌이 든다.
  * DP[i]를 i까지의 잡을 처리하는데에 드는 최소 코스트라고 하면, dp[i] = {j까지의 잡을 처리하는데 든 코스트} + {j번부터 i까지를 묶은 배치의 코스트} 형태로 표현이 될거 같다.
  * DP[i] = min_{j<i}(DP[j-1] + O[i]*(F[j]+...+F[i])) 이런식인데.. (F[j]+...+F[i])는 누적합을 이용해서 간단히 구한다 쳐도, O[i]가 문제이다. T[0]+T[1]+...+T[i] 에다가 {배치의 갯수}*S를 해줘야 O[i]가 나오는데.. 이러면 배치의 갯수를 따로 저장하고 있어야 한다.
    * j번부터 i까지를 배치로 묶을때, dp[j-1]가 최소인 경우가 유리할수도 있고 j-1까지를 묶을 배치의 수가 적은것이 더 유리할수도 있기 때문에 배치의 수에 따른 최소 코스트를 모두 킵하고 있어야 한다.. 결국 DP테이블이 DP[i][s] 이런식의 2차원 DP가 된다..
  * 하지만 이것을 역방향으로 DP식을 정리하는 방법을 생각해볼수 있다.
  * DP[i]를 0~i번 까지가 한개의 배치로 묶일때의 0~N-1까지를 전부 처리하는 최소 코스트라고 생각하자. 즉 배치를 나누는 구분이 i번 이후에만 존재하는 경우이다. 원래는 0~j까지가 한개의 배치로 묶였을때의 최솟값이 DP[j]였을텐데, DP[i]는 이 값에서 0~j를 0~i와 i+1~j 의 두개의 배치로 나눈 경우이다. DP[i]가 DP[j]에 비해서 어떻게 값이 변동되는지 생각해보자. 일단.. i+1번 이후의 잡에 대한 O 값은 전부 S씩 늘어난다. 그래서 S*(F[i+1]+...+F[N-1]) 가 총 코스트에 추가된다. 대신 0~i까지의 잡의 O값은 T[i+1]+...+T[j]만큼이 줄어든다. DP[j]에서는 i까지의 코스트가 (F[0]+...+F[i])*(T[0]+...+T[j])로 계산되었는데 i에서 배치를 나누면 (F[0]+...+F[i])*(T[0]+...+T[i])로 계산할수 있다.
  * 그럼 이제 식을 정리해보자. ST[x] = T[0]+..+T[x], SF[x] = F[0]+..+F[x] 로 누적합을 써서 표현하자. 
    * DP[i] = min_{j>i} {DP[j] + S*(SF[N-1] - SF[i]) + SF[i]*(ST[i] - ST[j])} 로 1차원 형태로 깔끔하게 표현된다!
  * 자 그리고 이제, i에 관한 텀을 기준으로 식을 다시 정리해보면 
    * DP[i] = min_{j>i} {-ST[j]*SF[i] + DP[j] + S*(SF[N-1]-SF[i])+SF[i]*ST[i]} 형태이므로 [[ps:cht]]를 이용해서 빠르게 계산할 수 있다. -ST[j]는 단조감소, SF[i]는 단조증가하므로 O(n)에 계산이 가능하다
  * 이제 식이고 최적화 방법이고 다 나왔으니 그대로 구현만 하면 되기는 하는데.. 구현할때 실수할 여지가 많기는 하다. 일단 위의 식은 DP[n-1]에서 출발해서 DP[n-2],dp[n-3],...을 채워나가는 식인데, 식이 꼬이기 쉽다. 그리고 teflib의 convexhulltrick.dp_with_cht 함수에 그냥 넣을수도 없다. DP'[i]= DP[N-1-i] 이런식으로 테이블을 다시 정의하고 0에서부터 출발해서 채우도록 바꾸는게 차라리 쉬웠다
    * ST[0]=0, ST[x] = T[0]+...+T[x-1] 로 정의를 살짝 바꾸고 식을 다시 쓰면 아래처럼 된다. (SF도 마찬가지)
    * DP'[0] = ST[N]*SF[N]
    * DP'[i] = min_{j<i} {-ST[N-j]*SF[N-i] + DP'[j] + S*(SF[N-1]-SF[N-i])+SF[N-i]*ST[N-i]}
  * 휴.. 이제 그냥 드디어 함수에 넣고 돌리면 된다.
  * 이렇게 해서 돌리면 겨우 80ms 정도만에 통과된다. [[ps:cht]]관련 문제들 중에서는 너무나도 빠르게 통과되는데, 옛날 문제라서 N값이 겨우 10000 이하로 주어지기 때문이다. (요즘 나오는 문제들은 N의 최댓값이 보통 100,000 이상이다.) 그래서 cpp로 돌리면 CHT를 사용하지 않는 O(n^2) 솔루션도 통과된다는듯 하다. 난이도가 플래티넘3 밖에 안되는 것은 이런 이유인듯


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 5498. Batch Scheduling".

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

Tags: [DP] [CHT]
"""

import sys
from teflib import convexhulltrick


def main():
    N = int(sys.stdin.readline())
    S = int(sys.stdin.readline())
    T_and_F = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    f_sum = [v := 0] + [v := v + f for t, f in T_and_F]
    t_sum = [v := 0] + [v := v + t for t, f in T_and_F]
    c = f_sum[-1] * S
    dp = [None] * (N + 1)
    dp[0] = t_sum[-1] * f_sum[-1]
    dp = convexhulltrick.dp_with_cht(
        cht=convexhulltrick.ConvexHullTrickForIncreasingQueries(),
        dp=dp,
        f_j=lambda j: t_sum[N - j],
        f_i=lambda i: -f_sum[N - i],
        g_j=lambda j: dp[j],
        g_i=lambda i: f_sum[N - i] * (t_sum[N - i] - S) + c,
    )
    print(dp[-1])


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: 
    * [[:ps:teflib:convexhulltrick#dp_with_cht|teflib.convexhulltrick.dp_with_cht]]
    * [[:ps:teflib:convexhulltrick#ConvexHullTrickForIncreasingQueries|teflib.convexhulltrick.ConvexHullTrickForIncreasingQueries]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}