Cod sursa(job #1346268)

Utilizator MihailPJack ONeill MihailP Data 18 februarie 2015 09:30:58
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct client
{
	int timp, pret;
};
void MERGE(struct client A[50000], int p, int q, int r)
{
	int i, j, k, n1, n2;
	struct client L[25000], R[25000];
	for (i = 1; i <= q - p + 1; i++)
	{
		L[i].pret = A[p + i - 1].pret;
		L[i].timp = A[p + i - 1].timp;
	}

	for (i = 1; i <= r - q; i++)
	{
		R[i].pret = A[q + i].pret;
		R[i].timp = A[q + i].timp;
	}

	n1 = q - p + 1;
	n2 = r - q;
	L[n1 + 1].timp = INT_MAX;
	R[n2 + 1].timp = INT_MAX;
	i = 1;
	j = 1;
	for (k = p; k <= r; k++)
	{
		if (L[i].timp <= R[j].timp)
		{
			A[k].timp = L[i].timp;
			A[k].pret = L[i].pret;
			i++;
		}
		else
		{
			A[k].timp = R[j].timp;
			A[k].pret = R[j].pret;
			j++;
		}
	}
}
void MERGE_SORT(struct client A[50000], int p, int r)
{
	int q;

	if (p < r)
	{
		q = (p + r) / 2;
		MERGE_SORT(A, p, q);
		MERGE_SORT(A, q + 1, r);
		MERGE(A, p, q, r);
	}
}
int profit(int P, struct client A[5000], int N, int C)
{
	int best, i, T, max = -1, nr = 1, castig;
	best = 0;
	A[0].timp = A[0].pret = -10;
	for (i = 1; i <= N; i++)
	{
		if (A[i].pret >= P)
		{
			castig = P;
		}
		else
		{
			castig = 0;
		}

		best = best + castig - (A[i].timp - A[i - 1].timp)*C;
		if (best < castig-C)
		{
			best = castig - C;
		}
		if (best>max)
			max = best;

	}
	if (best > max)
	{
		max = best;
	}
	return max;

}
int main()
{
	FILE *f, *g;
	f = fopen("carnati.in", "r");
	g = fopen("carnati.out", "w");
	int N, C, i, nr, max = -1, P, castig3, castig1, castig2, T, nr0 = 0;
	struct client A[50000];
	fscanf(f, "%d %d", &N, &C);
	for (i = 1; i <= N; i++)
	{
		fscanf(f, "%d %d", &A[i].timp, &A[i].pret);
	}

	MERGE_SORT(A, 1, N);

	for (i = 1; i <= N; i++)
	{
		T = profit(129, A, N, C);
		if (T > max)
		{
			max = T;
		}


	}

	fprintf(g, "%d", max);


}