Submission

Score: 80

User: mantaggez

Problemset: Fool's Compensation

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-23 19:39:10

#include <bits/stdc++.h>

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

const int nx = 1e4+5;

int n;
int 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(int 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) {
        //     if(cost[idx - 1] != cost[idx]) pq.push({r[idx + 1], idx}), pq.push({r[idx - 1], idx});
        //     cost[idx - 1] = cost[idx] = max(cost[idx - 1], cost[idx]);
        // }
        // if(r[idx + 1] == rate) {
        //     if(cost[idx + 1] != cost[idx]) pq.push({r[idx + 1], idx}), pq.push({r[idx - 1], idx});
        //     cost[idx + 1] = cost[idx] = max(cost[idx + 1], cost[idx]);
        // }
    }

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

    return 0;
}