Cod sursa(job #1456163)

Utilizator Salomia_Adrian_325CCSalomia Adrian Salomia_Adrian_325CC Data 29 iunie 2015 22:05:30
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

long long cautare_coordonata_stanga_jos(int *v, int n, int d) {
	long long *din1 = (long long *) malloc ((v[n-1]+1) * sizeof(long long));
	int k = 0, i, j;
	j = v[n-1] - d;
	din1[v[0]] = 0;
	while(v[k] == v[0]) {
		k++;
	}
	for(i = v[0]+1;i <= j;i++) {
		din1[i] = din1[i-1] + k;
		while(v[k] == i && k < n) {
			k++;
		}
	}

	long long *din2 = (long long *) malloc ((v[n-1]+1) * sizeof(long long));
	din2[j+1] =  0;
	k = n-1;
	for(i = j;i >= v[0];i--) {
		din2[i] = din2[i+1] + n - 1 - k;
		while(v[k] == i + d && k >= 0) {
			k--;
		}
	}

	long long z = 2500000000;
	for(i = v[0];i <= j;i++) {
		if(z > din1[i] + din2[i]) {
			z = din1[i] + din2[i];
		}
	}

	return z;
}

int main() {
	FILE *f1 = fopen("tribute.in", "r");
	FILE *f2 = fopen("tribute.out", "w");

	int n, d_x, d_y;
	fscanf(f1, "%d%d%d", &n, &d_x, &d_y);

	int *x = (int *) malloc (n * sizeof(int));
	int *y = (int *) malloc (n * sizeof(int));
	int i;
	for(i = 0;i < n;i++) {
		fscanf(f1, "%d%d", &x[i], &y[i]);
	}

	sort(x, x+n);
	sort(y, y+n);

	long long z1, z2;
	z1 = cautare_coordonata_stanga_jos(x, n, d_x);
	z2 = cautare_coordonata_stanga_jos(y, n, d_y);
	
	fprintf(f2, "%lld\n", z1+z2);

	fclose(f1);
	fclose(f2);
	return 0;
}