Cod sursa(job #464817)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 21 iunie 2010 20:33:03
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#define NMAX 50005
#define ll long long
int n,a,b;
int A[NMAX],B[NMAX];
ll rez1,rez2;
void read()
{
	scanf("%d%d%d",&n,&a,&b);
	int i,x,y;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		A[x]++; B[y]++;
	}
}
void precompute()
{
	int i;
	for (i=0; i<=50000; i++)
		A[i]+=A[i-1],B[i]+=B[i-1];
}
inline ll min(ll x,ll y)
{
	return x<y ? x : y;
}
void solve()
{
	int i;
	ll act=0;
	for (i=a+1; i<=50000; i++)
		act+=(ll)(A[i]-A[i-1])*(i-a);
	rez1=act;
	for (i=1; i<=50000-a; i++)
	{
		act+=A[i-1];
		act-=A[50000]-A[i+a-1];
		rez1=min(rez1,act);
	}
	act=0;
	for (i=b+1; i<=50000; i++)
		act+=(ll)(B[i]-B[i-1])*(i-b);
	rez2=act;
	for (i=1; i<=50000-b; i++)
	{
		act+=B[i-1];
		act-=B[50000]-B[i+b-1];
		rez2=min(rez2,act);
	}
}
int main()
{
	freopen("tribute.in","r",stdin);
	freopen("tribute.out","w",stdout);
	read();
	precompute();
	solve();
	printf("%lld\n",rez1+rez2);
	return 0;
}