102506: [AtCoder]ABC250 G - Stonks

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $600$ points

Problem Statement

You are going to trade stocks of Company X for the next $N$ days.

As a precognitive, you know that the stock price on the $i$-th day of trading will be $P_i$ yen (the currency in Japan) per unit.

Every day, you can choose to do exactly one of the following.

  • Buy one unit of stock for $P_i$ yen.
    • You will obtain one unit of stock and your money will decrease by $P_i$ yen.
  • Sell one unit of stock for $P_i$ yen.
    • You will lose one unit of stock and your money will increase by $P_i$ yen.
  • Do nothing.

You initially have $10^{100}$ yen, so you will never be short of money.

Find the maximum possible amount of money you will have gained when the $N$-th day has ended.
Even if you still possess some amount of stocks of Company X when the $N$-th day has ended, it is considered that they are worth $0$ yen.

Constraints

  • All values in input are integers.
  • $1 \le N \le 2 \times 10^5$
  • $1 \le P_i \le 10^9$

Input

Input is given from Standard Input in the following format:

$N$
$P_1$ $P_2$ $\dots$ $P_N$

Output

Print the answer as an integer.

Sample Input 1

8
2 5 4 3 7 1 8 6

Sample Output 1

16

By acting as follows, your money will increase by $16$ yen, which is the maximum possible.

  • On the $1$-th day, you buy $1$ unit of stock. You now have $1$ unit of stock, and your money has increased by $-2$ yen so far.
  • On the $2$-nd day, you sell $1$ unit of stock. You now have $0$ units of stocks, and your money has increased by $3$ yen so far.
  • On the $3$-rd day, you buy $1$ unit of stock. You now have $1$ unit of stock, and your money has increased by $-1$ yen so far.
  • On the $4$-th day, you buy $1$ unit of stock. You now have $2$ units of stocks, and your money has increased by $-4$ yen so far.
  • On the $5$-th day, you sell $1$ unit of stock. You now have $1$ unit of stock, and your money has increased by $3$ yen so far.
  • On the $6$-th day, you buy $1$ unit of stock. You now have $2$ units of stocks, and your money has increased by $2$ yen so far.
  • On the $7$-th day, you sell $1$ unit of stock. You now have $1$ unit of stock, and your money has increased by $10$ yen so far.
  • On the $8$-th day, you sell $1$ unit of stock. You now have $0$ units of stocks, and your money has increased by $16$ yen so far.

Sample Input 2

5
10000 1000 100 10 1

Sample Output 2

0

Sample Input 3

15
300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000

Sample Output 3

2787595378

Input

题意翻译

你要买一家公司的股票，现在你知道每天这个股票值 $p_i$ 元。 每天你要么买进一股，要么卖出一股，或者不操作，**不能进行多个操作**。 如果第 $n$ 天结束后还有剩余的股票，作废。 问你最多能得多少钱？注意，你最开始很富有，不会担心买不起股票。 $n \le 2 \times 10^5$，$p_i \le 10^9$。

Output

得分：600分 部分 问题描述 你将在接下来的N天内交易X公司的股票。 作为预知者，你知道第i天的交易日的股票价格为P_i日元（日本的货币单位）。 每天，你可以选择做以下事情之一。 - 以P_i日元的价格购买一个单位的股票。 - 你将获得一个单位的股票，你的资金将减少P_i日元。 - 以P_i日元的价格卖出一个单位的股票。 - 你将失去一个单位的股票，你的资金将增加P_i日元。 - 不做任何事情。 你最初有10^100日元，所以你永远不会缺钱。 当第N天结束时，你获得的最大可能资金是多少？ 即使在第N天结束时你还拥有X公司的一定数量的股票，也认为它们的价值为0日元。 部分 约束条件 - 输入中的所有值都是整数。 - 1≤N≤2×10^5 - 1≤P_i≤10^9 部分 输入格式 输入将从标准输入中按以下格式给出： N P_1 P_2 … P_N 部分 输出格式 输出一个整数。 部分 样例输入1 8 2 5 4 3 7 1 8 6 部分 样例输出1 16 通过以下行为，你的资金将增加16日元，这是可能的最大值。 - 在第1天，你购买1个单位的股票。你现在有1个单位的股票，到目前为止你的资金增加了-2日元。 - 在第2天，你卖出1个单位的股票。你现在没有股票，到目前为止你的资金增加了3日元。 - 在第3天，你购买1个单位的股票。你现在有1个单位的股票，到目前为止你的资金增加了-1日元。 - 在第4天，你购买1个单位的股票。你现在有2个单位的股票，到目前为止你的资金增加了-4日元。 - 在第5天，你卖出1个单位的股票。你现在有1个单位的股票，到目前为止你的资金增加了3日元。 - 在第6天，你购买1个单位的股票。你现在有2个单位的股票，到目前为止你的资金增加了2日元。 - 在第7天，你卖出1个单位的股票。你现在有1个单位的股票，到目前为止你的资金增加了10日元。 - 在第8天，你卖出1个单位的股票。你现在没有股票，到目前为止你的资金增加了16日元。 部分 样例输入2 5 10000 1000 100 10 1 部分 样例输出2 0 部分 样例输入3 15 300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000 部分 样例输出3 2787595378

Source/Category

加入题单

算法标签：