Cod sursa(job #2685594)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 17 decembrie 2020 12:16:06
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

ifstream fin("tribute.in");
ofstream fout("tribute.out");

int n, dx, dy;
pair<int, int> p[50100];
int cnt[50100];

int find_minimal_cost(int siz) {
	int top = 50000;
	int bottom = top - siz;
	
	int cnt_up = 0;
	int cnt_down = n;
	for (int i = top; i >= bottom; i--)
		cnt_down -= cnt[i];
		
	int sum_up = 0;
	int sum_down = 0;
	for (int i = bottom - 1; i >= 0; i--)
		sum_down += cnt[i] * (bottom - i);
	
	int best = sum_up + sum_down;
	while (bottom > 0) {
		sum_down -= cnt_down;
		cnt_down -= cnt[--bottom];
		cnt_up += cnt[top--];
		sum_up += cnt_up;
		best = min(best, sum_up + sum_down);
	} 
		
	return best;
}

int main() {
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(0);
	
	fin >> n >> dx >> dy;
	
	for (int i = 1; i <= n; i++) 
		fin >> p[i].first >> p[i].second;
	
	for (int i = 1; i <= n; i++)
		cnt[p[i].first]++;
	int ans = find_minimal_cost(dx);
	
	for (int i = 0; i <= 50000; i++)
		cnt[i] = 0;
	for (int i = 1; i <= n; i++)
		cnt[p[i].second]++;
	ans += find_minimal_cost(dy);
	
	fout << ans;
	return 0;
}