TLE '16 Contest 2 P1 - In Debt

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
ZQFMGB12 does not own a bank, contrary to what his friends believe.

ZQFMGB12 often loans money to other people. As a result, many people are in debt to him. Initially, on day 0, his friends collectively owe him $0. Over N days, numbered from 1 to N, one of his friends can either borrow money or return money that is owed to ZQFMGB12. It is possible that his friends return so much money such that he owes his friends back money (i.e. his friends owe him a negative amount).

After the N days of borrowing/returning, ZQFMGB12 acquires a time machine and would like to go back to the day where his friends have the most total debt. If there are multiple days where his friends have the most total debt, he wants to go the earliest one of them. Please determine which day this is!

Input Specification

The first line of input will contain an integer N (1 \leq N \leq 100\,000), the number of days.

N lines of input follow. The line can either be borrow x, signifying that x dollars are borrowed from ZQFMGB12 (increase in debt), or return x, signifying that x dollars has been returned to him (decrease in debt). x is guaranteed to be non-negative, and the absolute value of the total debt at any time will not exceed 10^9.

Output Specification

Output a single integer from 0 to N that signifies the earliest day where ZQFMGB12's friends owe him the most.

Sample Input

borrow 38
borrow 10
return 5
borrow 5
return 20

Sample Output


Explanation For Sample Output

On days 2 and 4, ZQFMGB12's friends owe him $48, the highest debt. He would want to go back to day 2 over day 4 since it is earlier.


There are no comments at the moment.