Pythonで競プロしてる 
株式会社すぬけのサービスを利用しようとしている高橋君が支払う必要のある最小の合計金額を求める問題です。
提出
n, c = map(int, input().split())
event = []
for i in range(n):
ai, bi, ci = map(int,input().split())
event.append([ai-1,ci])
event.append([bi,-ci])
event.sort()
ans = 0
num = 0
day = 0
for x, y in event:
if day != x:
ans += min(num,c)*(x-day)
day = x
num += y
print(ans)日程の最大値が小さい場合は、累積和のいもす法で導くことができますが、109と大きいため、工夫する必要があります。
一つのサービスを利用していると仮定し、そのサービスは、ai日にci円上がり、bi+1日に-ci円下がると考えます。
リスト「event」に、[ai-1,ci],[bi,-ci] を加えていきます。
これを日にちでソートし、合計値を「ans」に足していくことにします。
サービスの利用料金は「num」に入れます。
「day」には最初0を入れておき、「day」と「event」の中の x が異なるときに、その時のサービスの利用料金 num と、すぬけプライム C円を比較し、安い方と「x-day」を掛けたものを「ans」に足します。
「day」と x が異なるまでは、同じ料金が続いていくため、この計算で求められます。
