---
# System prepended metadata

title: Buýt Hà Nội T_T

---

# Buýt Hà Nội T_T
Ta sẽ DP theo chuyến, sort các chuyến theo thứ tự ngày tăng dần
$f[i]$ là số tiền ít nhất đi hết $i$ chuyến đầu. $(i \le 300000)$
$mi[j][i]$ là chuyến nhỏ nhất mà khi dùng loại giảm giá $j$ có thể miễn phí từ nó đến $i$.

for $j$ loại giảm giá:
$f[i]$ = $f[i - 1] + r$
$f[i]$ = min ($f[mi[j][i] - 1] + c[j]$)

$i$ - $mi[j][i]$ + $1$ $\le$ $k[j]$
ngày($i$) - ngày($mi[j][i]$) + $1$ $\le$ $d[j]$

tìm $mi[j][i]$ = chặt nhị phân $O(n*q*logq)$.
vì $mi[j][i] \le mi[j][i + 1]$ nên dùng con trỏ cbi trước $O(n*q)$
