Pagini recente » Borderou de evaluare (job #153604) | Cod sursa (job #3232141) | Infoarena Monthly 2014 - Clasament | Cod sursa (job #1252594) | Cod sursa (job #3142577)
#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];
suf[v[n - 1] + 1] = 0, cnt[v[n - 1] + 1] = 0;
sort(v.begin(), v.end());
int end = n - 1;
for(int i = v[n - 1];i >= 0;--i)
{
suf[i] = suf[i + 1];
cnt[i] = cnt[i + 1];
while(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] - cnt[next] * next;
sum += (ull) count * i - pref;
while(left < n && (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";
}