Pagini recente » Cod sursa (job #1082402) | Cod sursa (job #3142572)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int nmax = 50005;
ull suf[nmax], pref[nmax];
ull solve(vector<int>& v, int dx)
{
ull ans = LLONG_MAX;
int n = v.size();
ull suf[50005], cnt[50005];
sort(v.begin(), v.end());
suf[v[n - 1]] = v[n - 1];
cnt[v[n - 1]] = 1;
int end = n - 2;
for(int i = v[n - 1] - 1;i >= 0;--i)
{
suf[i] = suf[i + 1];
cnt[i] = cnt[i + 1];
if(end >= 0 && v[end] == i)
suf[i] += v[end--], ++cnt[i];
}
ull pref = 0;
int count = 0, left = 0;
for(int i = 0;i <= v[n - 1];++i)
{
int next = i + dx;
ull sum = 0;
if(next <= v[n - 1])
sum += suf[next] - (ull) cnt[next] * i;
sum += count * i - pref;
if(i == v[left])
pref += v[left++], ++count;
ans = min(ans, sum);
}
return ans;
}
int main() {
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
int n, dx, dy;
cin >> n >> dx >> dy;
vector<int> x(n), y(n);
for(int i = 0;i < n;++i)
cin >> x[i] >> y[i];
ull rx = solve(x, dx);
ull ry = solve(y, dy);
cout << rx + ry << "\n";
}