PythonでJOI難易度5を埋める #15 - taxfree

A - 鉄道旅行 (Railroad Trip)

考えたこと
鉄道 $i$ は $i$ と $i+1$ の区間しか移動できないから，それぞれの鉄道に何回乗るかをカウントする．カウントしたら $min(鉄道iに乗る回数 \times 紙の切符の値段, 鉄道iの乗る回数 \times ICカードで乗る値段 + ICカード代$ をそれぞれの鉄道で計算するだけだが，鉄道 $i$ に何回乗るかをカウントするのがネックになる．
愚直に区間内の配列の値を $+1$ すると，1→n→2 $\cdots$ みたいなときに $O(NM)$ ?になる可能性がある．そこで，累積和を用いて区間の最初と最後だけで更新できるように工夫する．
区間の最初を $+1$ することによって後ろの全要素に $+1$ したことになり，区間の最後を $-1$ するとそれ以降の全要素を $-1$ することになるので，区間内だけ $+1$ することができる．

n, m =map(int, input().split())
p = list(map(int, input().split()))
ticket = [list(map(int, input().split())) for _ in range(n - 1)]

cnt = [0] * (n - 1)
for i in range(m - 1):
    tmp = list(sorted([p[i], p[i + 1]]))
    cnt[tmp[0] - 1] += 1
    if tmp[1] != n:
        cnt[tmp[1] - 1] -= 1

csum = [cnt[0]]
for i in range(1, n - 1):
    csum.append(cnt[i] + csum[i - 1])

ans = 0
for i in range(n - 1):
    ans += min(ticket[i][0] * csum[i], ticket[i][1] * csum[i] + ticket[i][2])

print(ans)