Pagini recente » Cod sursa (job #930905) | Cod sursa (job #695676) | Cod sursa (job #990678) | Cod sursa (job #1971081) | Cod sursa (job #1771304)
#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);
if (pcur < 0) 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 = -1;
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;
}