CFJUN21 - Seller Bob

no tags 

Last year Bob earned by selling memory sticks. During each of n days of his work one of the two following events took place:

  • A customer came to Bob and asked to sell him a 2x MB memory stick. If Bob had such a stick, he sold it and got 2x berllars.
  • Bob won some programming competition and got a 2x MB memory stick as a prize. Bob could choose whether to present this memory stick to one of his friends, or keep it.

Bob never kept more than one memory stick, as he feared to mix up their capacities, and deceive a customer unintentionally. Now, knowing all the customers' demands and all the prizes won at programming competitions during the last n days, Bob wants to know, how much money he could have earned, if he had acted optimally.


The first input line contains number n (1 ≤ n ≤ 5000) — amount of Bob's working days. The following n lines contain the description of the days. Line sell x stands for a day when a customer came to Bob to buy a 2x MB memory stick (0 ≤ x ≤ 2000). It's guaranteed that for each x there is not more than one line sell x. Line win x stands for a day when Bob won a 2x MB memory stick (0 ≤ x ≤ 2000).


Output the maximum possible earnings for Bob in berllars, that he would have had if he had known all the events beforehand. Don't forget, please, that Bob can't keep more than one memory stick at a time.


win 10
win 5
win 3
sell 5
sell 3
win 10
sell 10
Output: 1056

hide comments
Nikhil Garg: 2010-09-20 16:11:27

I too have got Ac on codeforces. Also my algorithm should work despite multiple sell days.Are there any trivial things to take care of here?

.:: Pratik ::.: 2010-07-12 04:53:05

There are still cases with multiple sell days. Can this be fixed? My solution has gotten accepted at Codeforces.

Josef Ziegler: 2010-07-03 22:19:25

Testcase 10 still contains wrong input data! "It's guaranteed that for each x there is not more than one line sell x." is still not true...

Sandro: 2010-06-23 20:54:09

what did you change?
it still says "there is not more than one line sell x."

btw: it is imho quite relevant if this actually holds. there are greedy solutions which only work if there are no two "sell x" for some x
[feel free to delete if considered a hint...]

Phan Công Minh: 2010-06-23 05:36:41

I've changed the condition .

Oleg: 2010-06-22 13:52:17

Just update description then.

Last edit: 2010-06-22 17:59:25
Phan Công Minh: 2010-06-22 09:25:02

Thanks oleg. But i think the result won't change . how about you ?

Oleg: 2010-06-22 09:25:02


Please check test cases. I catch assert on "assert(sellDay[x] == -1);" - you have 2 or more sells with same x.

Added by:Phan Công Minh
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)