Cod sursa(job #3142575)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 22 iulie 2023 15:53:57
Problema Tribute Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#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] - cnt[next] * next;
		sum += (ull) 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";
}