Submission

Score: 90

User: august

Problemset: Fool's Compensation

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-22 17:41:52

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int,int>
const int INF = 1e18;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>> n;

    vector<pi> a;
    vector<int> b(n+2,0), val(n+2, 0);

    for (int i=1; i<=n; i++) {
        pi cur;
        cin>> cur.first;
        cur.second = i;
        a.push_back(cur);
        b[i] = cur.first;
    }

    sort(a.begin(), a.end());

    int cost = 0;
    for (int i=0; i<n; i++) {
        pi cur = a[i];
        int v = cur.first, id = cur.second;

        int mx = 0;
        if (b[id] > b[id-1]) mx = max(mx, val[id-1]);
        if (b[id] > b[id+1]) mx = max(mx, val[id+1]);

        mx += 1000;
        val[id] = mx;
    }

    
    int i=1;
    while (i<=n) {
        int j=i+1;
        int mx=val[i];
        while (b[i] == b[j] && j<=n) mx=max(mx, val[j]), j++;
        cost += mx * (j-i);

        i=j;
    }
    cout<< cost;
}
/*

10
3
3
3
3
3
3
3
2
1
0

*/