Pagini recente » Cod sursa (job #3169542) | Cod sursa (job #167669) | Cod sursa (job #2266587) | Cod sursa (job #2131173) | Cod sursa (job #2698391)
// Mihai Priboi
#include <bits/stdc++.h>
#define MAXN 2000
struct customer { int p, t; } v[MAXN];
int compar( const customer& a, const customer& b ) {
return a.t < b.t;
}
int main() {
FILE *fin, *fout;
int n, c, i, j, price, profit, last_time, max, loss;
fin = fopen( "carnati.in", "r" );
fscanf( fin, "%d%d", &n, &c );
for( i = 0; i < n; i++ )
fscanf( fin, "%d%d", &v[i].t, &v[i].p );
fclose( fin );
// sortam dupa ora la care intra persoanele
std::sort( v, v + n, compar );
max = 0;
// pentru fiecare pret posibil (pe care are sens sa il incercam) verificam profitul maxim (ssm)
for( i = 0; i < n; i++ ) {
price = v[i].p;
// tratam separat primul numar pentru ca nu platim vanzatorul pana in primul moment (suntem zgarciti)
profit = 0;
if( v[0].p >= price )
profit = price;
max = std::max( profit - c, max );
last_time = v[0].t;
for( j = 1; j < n; j++ ) {
loss = ( v[j].t - last_time ) * c;
last_time = v[j].t;
// >= ca sa nu platim vanzatorul mai mult decat e necesar (chiar daca nu schiba profitul)
if( loss >= profit )
profit = 0;
else
profit -= loss;
if( v[j].p >= price )
profit += price;
// temporar, ora se completeaza doar daca e ultima
profit -= c;
max = std::max( profit, max );
profit += c;
}
}
fout = fopen( "carnati.out", "w" );
fprintf( fout, "%d", max );
fclose( fout );
return 0;
}