#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>
ll n, m, k;
ll a[dim], dp[dim];
int main() {
ll u, w,q, v, y;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
}
ll mx=0;
map<ll, ll> mp;
for(int i=1; i<=n; i++){
mx=max(mx, a[i]);
a[i]=mx;
mp[a[i]]++;
}
vector<pll> g;
for(auto x: mp){
g.pb(x);
}
sort(g.begin(), g.end());
ll sz=0;
ll len=g.size();
for(int i=0; i<len-1; i++){
ll mx1=g[i].fi;
ll gs=g[i].se;
sz+=gs;
ll mx2=g[i+1].fi;
ll sz2=g[i+1].se;
if((mx2-mx1)*gs<=(mx1*sz2)){
g[i].fi=0;
g[i+1].se+=g[i].se;
}
}
vector<pll> res;
for(int i=0; i<len; i++){
if(g[i].fi==0)continue;
res.pb(g[i]);
}
len=res.size();
ll ans=0;
ll wait=0;
for(auto x: res){
ans+=((x.fi+wait))*(x.se);
wait+=x.fi;
}
cout<<ans<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |