以下の条件を満たす数列 \(A\) を考えます。

• \(A_{i} \in \{-1, 0, 1\}\)
• \(\forall i = 1, 2, \dots , N : \sum_{k = 1}^{i}A_{i}\leq 0\)

以下の値の最大値を求められれば良いです。

\[\sum_{i = 1}^{N}A_{i}P_{i}\]

\(A_{i}\) の全てに \(1\) を足します。すると答えは \(\sum P\) だけ増えます。このとき、 \(A\) は以下の条件を全て満たします。

• \(A_{i} \in \{ 0, 1, 2\}\)
• \(\forall i = 1, 2, \dots , N : \sum_{k = 1}^{i}A_{i}\leq i\)
• \(\sum A_{i} = N\)

これらを満たす \(A\) は全て以下の方法で構築することができます。

• 初め \(A_{i} = 2\) で初期化する
• \(i = 1, 2, ..., N\) の順に、以下の操作をする
  • \(j \leq i\) かつ \(A_{j} \neq 0\) を満たす \(j\) をひとつ選び、\(A_{j} -= 1\) をする。

ここで、\(j\) を選ぶ際にわざわざ \(P_{j}\) が大きいもの選んでも何の価値にもなりません。

よって、この \(j\) を選ぶ際、\(P_{j}\) が最小のものを選ぶという貪欲が正しいです。

この貪欲は priority queue を用いて簡単に実装することができます。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    int N;
    cin >> N;
    ll ans = 0;
    priority_queue<ll> pq;
    while(N--){
        ll a;
        cin >> a;
        ans += a;
        pq.push(-a), pq.push(-a);
        ans += pq.top();
        pq.pop();
    }
    cout << ans << "\n";
}