AlgoLensArena
ContestlərProblemlərOtaqlar
Vizualizator
← Məsələlər

FPC21-005.Bitcoin Bubble

Easy · 1 s · 256 MB

  • icpc
  • fpc
  • 2021

These days, all eyes and money are on crypto. The stakes are high and a team of experts, which call themselves the FPC (Fabulous People of Crypto) are on the verge of a big move. They call their move “The Bubble”.

The Bubble will work as follows: one day, the FPC will release a set of classified information that will shake the market to its roots. That day, call it xxx, will be the epicenter of their move. To measure the impact of The Bubble, consider the longest sequence of consecutive days, starting on day aaa and ending on day bbb (a≤x≤ba\leq x\leq ba≤x≤b), for which Bitcoin's price is never lower than its price on day xxx. The impact is measured as the length of this sequence in days multiplied by the price of Bitcoin on day xxx. The starting day and the end day of The Bubble's impact should be within the boundaries of the period the FPC know the price for.

There is only one catch: despite anticipating Bitcoin's price for the foreseeable future, the FPC lack the most fabulous skill in the world: programming. Help them measure the biggest possible impact of The Bubble, given that they release the shocking information on an optimal day.

Giriş formatı

The input consists of:

• A line with a single integer nnn (1≤n≤5⋅1041\leq n\leq 5\cdot 10^41≤n≤5⋅104), the number of price anticipations for Bitcoin.

• nnn lines, each containing two integers ppp and ddd (0≤p≤2⋅1090\leq p\leq 2\cdot 10^90≤p≤2⋅109 and 1≤d≤5⋅1041\leq d\leq 5\cdot 10^41≤d≤5⋅104), representing the price and the number of days the price lasts for.

Price information is given in chronological order.

Çıxış formatı

Output a single number, the biggest impact The Bubble can have.

Qeyd

Source: Freshmen Programming Contest 2021 · Author: Dragos Vecerdea · License: CC BY-SA 4.0 · Original: https://fpc.wisv.ch · Statement adapted for AlgoLens and shared under the same license.

Nümunələr

Giriş #1

4
3 2
9 4
5 2
7 4

Çıxış #1

50

Giriş #2

10
5 5
8 1
8 3
9 1
0 6
1 6
1 5
6 2
6 5
9 6

Çıxış #2

78