Županijsko natjecanje iz informatike 2019. / Druga podskupina (3. i 4. razred) - 3. zadatak

Mali Ogi u slobodno vrijeme proučava burzu.

Jednoga dana pronašao je godišnje izvješće prodaja i kupovina dionica tvrtke Jadranska Solana.

Izvješće se sastoji od N kronološki poredanih zapisa od kojih svaki označava zahtjev za kupnjom ili prodajom jedne dionice tvrtke po određenoj cijeni.

Točnije, za svaki od N zapisa poznate su dvije informacije: Si – vrsta zahtjeva (kupnja ili prodaja), te Xi – ponuđena cijena.

Gledajući ove brojeve, Ogi se zapitao koliko bi najviše mogao zaraditi tijekom dane godine na kupnji i prodaji dionica Jadranske Solane.

Za svaki zahtjev za prodajom, Ogi može odlučiti kupiti točno jednu dionicu po ponuđenoj cijeni; te za zahtjev za kupnjom, Ogi može odlučiti prodati točno jednu dionicu po ponuđenoj cijeni ako u tom trenutku posjeduje barem jednu dionicu.

Iako već zna da burza ne funkcionira tako jednostavno, pretpostavio je da zahtjevi na burzi ne ovise o njegovim postupcima, to jest da bi se isti niz zahtjeva dogodio čak i da je on trgovao na burzi.

Također, kako se u izvješću ne nalaze informacije o tome kada je neki zahtjev povučen, Ogi može kupiti ili prodati dionicu jedino u trenutku kada je postavljen određeni zahtjev.

Da ne bi morao brinuti oko detalja, Ogi pretpostavlja da na početku ima neograničen kapital te da ne posjeduje nijednu dionicu.

Kako je hrvatska burza vrlo prometna te se izvješće sastoji od velikog broja zapisa, Ogi vas je zamolio da napišete program koji će izračunati najveću moguću zaradu na dionicama Jadranske Solane.

Zaradu definiramo kao ukupan iznos dobiven prodajom dionica umanjen za ukupan iznos potrošen na kupnju dionica.

ULAZNI PODACI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 500 000), broj zapisa na burzi.

U idućih N redaka nalaze se po dva prirodna broja Si (1 ≤ Si ≤ 2) i Xi (1 ≤ Xi ≤ 109) odvojeni razmakom.

Ako je Si = 1, tada i -ti zapis opisuje zahtjev za kupnjom jedne dionice.

U suprotnom je Si = 2, te i-ti zapis opisuje zahtjev za prodajom jedne dionice. Xi označava ponuđenu cijenu kupnje/prodaje.

IZLAZNI PODACI

U jedini redak ispišite traženu najveću moguću zaradu.

PRIMJERI TEST PODATAKA

Ulaz

5
2 2
1 5
2 1
1 4
1 6

Izlaz

8

Objašnjenje

Pojašnjenje prvog primjera:

Prvi zapis: Ogi kupuje dionicu po cijeni 2.

Drugi zapis: Ogi prodaje dionicu po cijeni 5.

Treći zapis: Ogi kupuje dionicu po cijeni 1.

Četvrti zapis: Ogi odlučuje ne prodati dionicu po cijeni 4.

Peti zapis: Ogi prodaje dionicu po cijeni 6.

Ogijeva ukupna zarada: -2 + 5 - 1 + 6 = 8.

Ulaz

3
2 200
1 100
2 50

Izlaz

0

Objašnjenje

Pojašnjenje drugog primjera: Jedina je mogućnost zarade prodati dionicu za cijenu 100, no prije toga morao bi ju kupiti po višoj cijeni.

U ovom primjeru najisplativija je strategija ne trgovati te je stoga

Ogijeva zarada 0.

Ulaz

6
2 20
2 40
2 30
1 10
1 70
1 50

Izlaz

70