Cod sursa(job #1015963)

Utilizator ELHoriaHoria Cretescu ELHoria Data 25 octombrie 2013 15:08:19
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
 
using namespace std;
 
ifstream cin("tribute.in");
ofstream cout("tribute.out");

const int CMAX = 50002;
int N, D[2];
int cnt[2][CMAX];
int num[2][CMAX];

int main()
{
	cin>>N>>D[0]>>D[1];
	int a, b;
	for(int i = 1;i <= N;i++) {
		cin>>a>>b;
		a++, b++;
		cnt[0][a] += a;
		cnt[1][b] += b;
		num[0][a]++;
		num[1][b]++;
	}

	for(int i = 1;i < CMAX;i++) {
		cnt[0][i] += cnt[0][i - 1];
		cnt[1][i] += cnt[1][i - 1];
		num[0][i] += num[0][i - 1];
		num[1][i] += num[1][i - 1];
	}

	long long minC[2] = {1ll<<55,1ll<<55};

	for(int i = 1;i < CMAX;i++) {
		for(int k = 0;k < 2;k++) {
			int left = i - 1;
			int right = min(CMAX - 1,i + D[k]);
			minC[k] = min(minC[k],1ll*i*num[k][left] - cnt[k][left] + (cnt[k][CMAX - 1] - cnt[k][right]) - 1ll*(i + D[k])*(num[k][CMAX - 1] - num[k][right]));
		}
	}

	cout<<minC[0] + minC[1];
    return 0;
}