Cod sursa(job #1771342)

Utilizator preda.andreiPreda Andrei preda.andrei Data 5 octombrie 2016 15:01:36
Problema Carnati Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <stdio.h>

#define MAX_CLIENTI 2001

typedef struct
{
	int timp, pret;
} Client;

Client clienti[MAX_CLIENTI];

int Max(int a, int b)
{
	return a > b ? a : b;
}

void Interschimba(Client *a, Client *b)
{
	Client aux = *a;
	*a = *b;
	*b = aux;
}

void Sorteaza(int st, int dr)
{
	if (st >= dr) return;

	int i = st + 1, j = dr;
	Interschimba(&clienti[st], &clienti[st + (dr - st) / 2]);

	while (i <= j) {
		while (i <= j && clienti[st].timp >= clienti[i].timp) ++i;
		while (i <= j && clienti[st].timp < clienti[j].timp) --j;
		if (i <= j) {
			Interschimba(&clienti[i], &clienti[j]);
			++i;
			--j;
		}
	}
	--i;
	Interschimba(&clienti[st], &clienti[i]);

	Sorteaza(st, i - 1);
	Sorteaza(i + 1, dr);
}

int AflaProfit(int n, int salariu, int pret)
{
	int pmax = 0, pcur = 0, i;

	for (i = 1; i <= n; ++i) {
		pcur -= salariu * (clienti[i].timp - clienti[i - 1].timp);
		pcur = Max(pcur, 0);

		if (clienti[i].pret >= pret) {
			if (pcur == 0) pcur = -salariu;
			pcur += pret;
		}

		pmax = Max(pmax, pcur);
	}

	return pmax;
}

int main()
{
	FILE *fin = fopen("carnati.in", "r");
	FILE *fout = fopen("carnati.out", "w");

	int n, salariu, i;
	fscanf(fin, "%d%d", &n, &salariu);

	for (i = 1; i <= n; ++i)
		fscanf(fin, "%d%d", &clienti[i].timp, &clienti[i].pret);
	clienti[0].timp = -200;
	Sorteaza(1, n);

	int profit_max = 0;
	for (i = 1; i <= n; ++i) {
		if (clienti[i].pret > salariu)
			profit_max = Max(profit_max, AflaProfit(n, salariu, clienti[i].pret));
	}

	fprintf(fout, "%d", profit_max);
	return 0;
}