Bitcoin
là một loại tiền mã hóa, được phát minh bởi Satoshi Nakamoto dưới dạng phần mềm
mã nguồn mở từ năm 2009. Bitcoin có thể được trao đổi trực tiếp bằng thiết bị kết
nối Internet mà không cần thông qua một tổ chức tài chính trung gian nào.
Sắn tìm hiểu và rất thích BITCOIN, cậu
dự đoán giá của Bitcoin trong N ngày tiếp theo là d1, d2,
…, dn (đơn vị USD). Cậu ta nhờ bố giúp đỡ để có thể thu lời từ việc
mua bán Bitcoin. Bố cậu ta có thể cho cậu ta mượn 1 đồng Bitcoin với hai điều
kiện:
- Một là phải trả phí: Mượn một ngày
trả phí K đô la. Khi trả lại phải đúng 1 Bitcoin và tiền lời.
- Hai là cho mượn bất cứ ngày nào
nhưng chỉ được bán đi và mua lại một lần duy nhất để kiếm lời.
Sắn đã có kế hoạch cho riêng mình để
thu lời. Cậu ấy có thể bán ra đồng Bitcoin vào một ngày bất kỳ nào đó nếu muốn
và mua lại vào một ngày nào đó sau ngày bán hoặc là không mua bán lần nào nếu
không thu được tiền lời. Đố bạn Sắn sẽ thu được nhiều nhất bao nhiêu tiền nếu
có kế hoặc bán tối ưu.
Dữ liệu nhập:
- Dòng 1 là hai số nguyên N và K (1 ≤ N ≤ 2*105; 0 ≤ K ≤ 105)
- Dòng 2 là giá Bitcoin trong n ngày tiếp theo d1, d2,
…, dn. (0 ≤ di ≤ 108)
Kết quả: In ra một số nguyên duy nhất là
số tiền lời tối đa mà Sắn thu được.
Ví dụ:
|
Input |
Output |
|
3
1 10
8 5 |
3 |
Trong ví dụ trên:
- Sắn bán ra ở ngày 1 thu được 10
USD
- Sắn mua lại Bitcoin ở ngày thứ 3 mất
5 USD
- Tiền lời thu được: 10 – 5 – 2 = 3
USD (2 USD là tiền lãi phải trả cho bố sau 2 ngày mượn).
CODE:
Đăng nhận xét