# Untitled

unknown
c_cpp
a year ago
1.2 kB
3
Indexable
Never
```class Solution {
public:
using ll = long long;
long long minCost(vector<int>& nums, vector<int>& cost) {
int n = nums.size();
ll largest = -1;
vector<pair<ll, ll>> pairs(n);

for (int i=0; i<n; ++i){
pairs[i] = {nums[i], cost[i]};
largest = max(largest, (ll) nums[i]);
}

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

vector<ll> prefix(n+1), suffix(n+1);
prefix[0] = 0; suffix[n] = 0;
ll initial = pairs[0].first;
ll initial_cost = 0;

for (int i=0; i<n; ++i){
prefix[i+1] = prefix[i] + pairs[i].second;
suffix[n-i-1] = suffix[n-i] + pairs[n-i-1].second;
initial_cost += (pairs[i].first - initial) * pairs[i].second;
}

vector<ll> costs(largest+1, LLONG_MAX);
costs[initial] = initial_cost;

for (int i=initial+1; i<=largest; ++i){
pair<ll, ll> curr = {i, 0};
int idx = lower_bound(pairs.begin(), pairs.end(), curr) - pairs.begin();
costs[i] = costs[i-1] + prefix[idx] - suffix[idx];
}

ll ans = *min_element(costs.begin(), costs.end());
return ans;
}
};```