たのしいたのしい家庭菜園
题意翻译
- 有 $n$ 棵树,第 $i$ 棵树的高度为 $h_i$,卖掉上面的果子会得到收益 $p_i$,拔掉需要代价 $c_i$。
- 第 $i$ 棵树结果需要满足 $[h_1,h_{i-1}]$ 中没有比 $h_i$ 大的,或者 $[h_{i+1},h_n]$ 中没有比 $h_i$ 大的,满足一者即可。
- 最后得到的总利润为卖掉果子得到的收益减去拔掉树需要的代价,求总利润的最大值。
- 对于 $100\%$ 的数据,$3 \le n \le 10^5$,$1 \le h_i,c_i,p_i \le 10^9$。
- Translated by 一只书虫仔。
题目描述
[problemUrl]: https://atcoder.jp/contests/joisc2015/tasks/joisc2015_c