Heroes of Money and Magic - 题目

Boondex 公司最近完成了 IPO 流程，现在其股票在证券交易所上市交易。目前，该公司拥有一段时间内的股票价格历史记录。为了举办一次新的营销活动，公司希望计算出，如果有人在这段时间内投机交易 Boondex 的股票，最多能赚到多少钱。

Boondex 的股票在进行买入/卖出操作时是不可分割的（即必须交易整数股）。这些股票的流动性极高，因此在证券交易所上对 Boondex 股票的任何操作都可以在任何时间以任何数量执行。

证券交易所对投资者执行的每次操作收取一定的费用。该费用为固定金额。对于“买入股票”操作，费用在交易前收取；对于“卖出股票”操作，费用在交易后收取。如果由于投资者资金不足而无法支付费用，则不允许进行该操作。

投资者必须在最后一天的结束前卖出其持有的所有 Boondex 股票。

输入的第一行包含三个整数 $N$、$M$ 和 $F$ —— 分别表示有价格信息的总天数（$1 \le N \le 10^5$）、投资者初始拥有的资金量（$1 \le M \le 10^5$）以及每次交易操作的费用 $F$（$1 \le F \le 10^5$）。

接下来的 $N$ 行，每行包含一个整数 $P_i$（$1 \le P_i \le 10^5$）—— 表示第 $i$ 天 Boondex 单股股票的价格。

保证本题的答案小于 $10^{18}$。

第一行输出投资者在 $N$ 天后最多可能拥有的资金量。

接下来的 $N$ 行应指示投资者每天在证券交易所的操作，以达到该最大资金：输出一个正数表示当天应买入的股票数量，输出一个负数表示当天应卖出的股票数量，如果当天不进行任何操作则输出 $0$。

QOJ.ac