Pagini recente » Cod sursa (job #278746) | Cod sursa (job #671163) | Cod sursa (job #1204590) | Cod sursa (job #1755402) | Cod sursa (job #1743966)
# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# define MAX_N 20000
using namespace std;
struct client {
int t, p;
} v[1 + MAX_N];
int n, c;
bool cmp_t( client a, client b ) {
return a.t <= b.t;
}
int S[1 + MAX_N];
int profit( int p ) {
int i, b;
b = 0;
for ( i = 1; i <= n; i ++ )
b = max( b, S[i] = ( p * ( v[i].p >= p ) + max( 0, S[i - 1] - c * ( v[i].t - v[i - 1].t ) ) ) );
return max( b - c, 0 );
}
int main() {
FILE *fin = fopen( "carnati.in", "r" ), *fout = fopen( "carnati.out", "w" );
int i, max, r, d;
fscanf( fin, "%d%d", &n, &c );
for ( i = 1; i <= n; i ++ )
fscanf( fin, "%d%d", &v[i].t, &v[i].p );
sort( v + 1, v + n + 1, cmp_t );
v[0].t = v[1].t;
max = 0;
for ( i = 1; i <= n; i ++ ) {
r = profit( v[i].p );
if ( r > max )
max = r;
}
fprintf( fout, "%d", max );
fclose( fin );
fclose( fout );
return 0;
}