Submission

Score: 100

User: meme_boi2

Problemset: Fool's Compensation

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-19 09:26:03

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int,2>
priority_queue <pii,vector<pii>,greater<pii>> pq;
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> mat(n+2,1e5+222);
    int j = 0, add = 0;
    vector<int> ans(n+2,0),cnt(n+2,0);
    for(int i = 1; i <= n; i++){
        cin >> mat[i];
        if(mat[i] != mat[i-1]){
            j++;
            pq.push({mat[i],j});
            cnt[j] = 1;
            add = 1;
        }else{
            add++;
            cnt[j] = add;
        }
    }
    
    while(!pq.empty()){
        auto [val,idx] = pq.top();
        pq.pop();
        ans[idx] = max(ans[idx-1],ans[idx+1]) +1;
    }
    int sum = 0;
    for(int i = 1; i <= j; i++) { 
        sum += ans[i]*cnt[i];
    //    cout << ans[i]*cnt[i] << ' ';
    }
    cout << 1000ll*sum;
}
/*
c2_su65_foolcomp

cd "c:\Users\RICOH-NB110\Desktop\Computer Programing\gchan\" ; if ($?) { g++ c2_su65_foolcomp.cpp -o c2_su65_foolcomp } ; if ($?) { .\c2_su65_foolcomp}

10
3
3
3
3
3
3
3
2
1
0
*/