Bệ phóng năng lượng

Buổi 24 — Mock Contest Phase 1
Points
10
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Có $N$ bệ đá xếp thành một hàng ngang đánh số từ $1$ đến $N$, bệ đá thứ $i$ có độ cao $H_i$. Ban đầu bạn đứng ở bệ đá $1$ và muốn di chuyển tới bệ đá $N$.

Từ bệ đá $i$, bạn có thể nhảy tới bệ đá $i+1$ hoặc $i+2$ (nếu không vượt quá $N$). Thông thường, chi phí nhảy từ bệ $i$ sang bệ $j$ là $|H_i - H_j|$. Tuy nhiên, một số bệ đá được trang bị bệ phóng: nếu bạn nhảy từ một bệ đá có bệ phóng, chi phí cho bước nhảy đó bằng $0$ (bất kể độ cao chênh lệch).

Tìm tổng chi phí nhỏ nhất để đi từ bệ $1$ đến bệ $N$.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $H_1, H_2, \dots, H_N$ ($1 \le H_i \le 10^9$).
  • Dòng thứ ba chứa xâu nhị phân $S$ độ dài $N$, trong đó $S_i = 1$ nếu bệ đá $i$ có bệ phóng, ngược lại $S_i = 0$.
Dữ liệu ra
  • Một số nguyên duy nhất là chi phí nhỏ nhất để đi từ $1$ đến $N$.
Ví dụ
Input Output
5
10 30 40 20 50
01000
30
4
10 100 10 100
0000
90
Giới hạn
  • $1 \le N \le 10^5$.
  • $1 \le H_i \le 10^9$.
Draft saved