Bob bán thẻ nhớ

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Bob bán thẻ nhớ trong $n$ ngày làm việc. Trong mỗi ngày, một trong hai sự kiện sau xảy ra:

Một khách hàng đến và hỏi mua thẻ nhớ có dung lượng $2^{x}$ MB. Nếu Bob đang có thẻ nhớ dung lượng đúng $2^{x}$ MB, anh ấy bán nó và nhận về $2^{x}$ berllar.
Bob thắng một cuộc thi lập trình và được tặng thẻ nhớ dung lượng $2^{x}$ MB. Bob có thể chọn giữ thẻ nhớ này hoặc tặng cho bạn.

Bob không bao giờ giữ quá một thẻ nhớ cùng lúc, vì sợ nhầm dung lượng và bán nhầm cho khách. Đảm bảo rằng với mỗi giá trị $x$ có tối đa một khách hàng muốn mua thẻ nhớ $2^{x}$ MB.

Biết trước toàn bộ thông tin về các khách hàng và các giải thưởng trong $n$ ngày, hãy giúp Bob tính số tiền lớn nhất anh ấy có thể kiếm được nếu hành động tối ưu.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ — số ngày làm việc của Bob.
n dòng tiếp theo, mỗi dòng có dạng sell x hoặc win x:
- sell x — ngày này một khách đến hỏi mua thẻ nhớ $2^{x}$ MB.
- win x — ngày này Bob được tặng thẻ nhớ $2^{x}$ MB.

Dữ liệu ra

In ra một số nguyên duy nhất — số tiền lớn nhất Bob có thể kiếm được (tính bằng berllar).

Ràng buộc

$1 \leq n \leq 5000$
$0 \leq x \leq 2000$
Với mỗi $x$ có tối đa một dòng sell x.

Ví dụ

Input	Output	Giải thích
7 win 10 win 5 win 3 sell 5 sell 3 win 10 sell 10	1056	Bob giữ thẻ $2^{5}$ MB ngày 2, bán ngày 4 (được $32$ ). Sau đó giữ thẻ $2^{10}$ MB ngày 6, bán ngày 7 (được $1024$ ). Tổng: $32 + 1024 = 1056$ .
3 win 5 sell 6 sell 4	0	Khách chỉ hỏi mua $2^{6}$ và $2^{4}$ , nhưng Bob chỉ có $2^{5}$ . Không bán được gì.

Bình luận

Không có bình luận tại thời điểm này.