Pagini recente » Cod sursa (job #34090) | Cod sursa (job #397244) | Cod sursa (job #473906) | Cod sursa (job #293546) | Cod sursa (job #481129)
Cod sursa(job #481129)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int NMAX = 50050;
const int INF = 1000000000;
int N, Dx, Dy;
int Tx, Ty, Txb, Tyb;
int x[NMAX], y[NMAX];
int xmax = -1, ymax = -1;
int rez1 = INF, rez2 = INF;
void citire()
{
cin >> N >> Dx >> Dy;
for(int i = 1 ; i <= N ; i++)
{
cin >> x[i] >> y[i];
xmax = max(xmax, x[i]);
Tx += x[i];
/*if(x[i] == 0)
Dx++;*/
ymax = max(ymax, y[i]);
Ty += y[i];
/*if(y[i] == 0)
Dy++;*/
}
}
void baleiere_x()
{
int nrx[NMAX];
int ind = 0;
for(int i = 0 ; i <= xmax ; i++)
{
while(x[ind + 1] == i)
ind++;
nrx[i] = ind;
}
for(int i = 0 ; i < Dx ; i++)
Tx -= (nrx[xmax] - nrx[i]);
for(int i = 0 ; i <= xmax - Dx ; i++)
{
rez2 = min(rez2, Tx + Txb);
Tx -= (nrx[xmax] - nrx[i + Dx]);
Txb += nrx[i];
}
}
void baleiere_y()
{
int nry[NMAX];
int ind = 0;
for(int i = 0 ; i <= ymax ; i++)
{
while(y[ind + 1] == i)
ind++;
nry[i] = ind;
}
for(int i = 0 ; i < Dy ; i++)
Ty -= (nry[ymax] - nry[i]);
for(int i = 0 ; i <= ymax - Dy ; i++)
{
rez1 = min(rez1, Ty + Tyb);
Ty -= (nry[ymax] - nry[i + Dy]);
Tyb += nry[i];
}
}
int main()
{
freopen("tribute.in", "r", stdin);
freopen("tribute.out", "w", stdout);
citire();
sort(x + 1, x + N + 1);
sort(y + 1, y + N + 1);
baleiere_x();
baleiere_y();
printf("%d\n", rez1 + rez2);
return 0;
}