Submission

Score: 100

User: mantaggez

Problemset: Fool's Compensation

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-23 19:42:01

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const ll nx = 1e4+5;

ll n;
ll r[nx], cost[nx];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    fill(cost, cost + nx, 1000);
    for(ll i=1;i<=n;i++) {
        cin >> r[i];
        pq.push({r[i], i});
    }

    while(!pq.empty()) {
        auto [rate, idx] = pq.top();
        pq.pop();
        // cout << rate << ' ' << idx << '\n';
        if(r[idx - 1] > rate) {
            cost[idx - 1] = max(cost[idx - 1], cost[idx] + 1000);
        }
        if(r[idx + 1] > rate) {
            cost[idx + 1] = max(cost[idx + 1], cost[idx] + 1000);
        }
        if(r[idx - 1] == rate && cost[idx - 1] < cost[idx]) {
            cost[idx - 1] = cost[idx];
            pq.push({r[idx - 1], idx - 1});
        }
        if(r[idx + 1] == rate && cost[idx + 1] < cost[idx]) {
            cost[idx + 1] = cost[idx];
            pq.push({r[idx + 1], idx + 1});
        }
    }

    ll ans = 0;
    for(ll i=1;i<=n;i++) {
        // cout << i << " : " << cost[i] << '\n';
        ans += cost[i];
    }
    cout << ans << '\n';

    return 0;
}