Pagini recente » Borderou de evaluare (job #353265) | Borderou de evaluare (job #1340274) | Borderou de evaluare (job #1688025) | Borderou de evaluare (job #883922) | Cod sursa (job #300518)
Cod sursa(job #300518)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INPUT "carnati.in"
#define OUTPUT "carnati.out"
#define SET(X) memset(X, 0, sizeof(X))
const int NMAX = 2001;
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
long N, M;
long T[ NMAX ], C[ NMAX ], P[ NMAX ];
void readData()
{
fscanf(fin, "%ld %ld", &N, &M);
for(long i = 1; i <= N; ++i)
{
fscanf(fin, "%ld %ld", &T[ i ], &C[ i ]);
P[ i ] = i;
}
}
inline int cmp(long X, long Y)
{
return T[ X ] < T[ Y ];
}
void solve()
{
long profMax = 0, G;
long DP[ NMAX ];
for(long i = 1; i <= N; ++i)
{
SET(DP);
DP[ 0 ] = 0;
P[ 0 ] = 0, T[ 0 ] = 0;
for(long j = 1; j <= N; ++j)
{
G = 0;
if(C[ P[i] ] <= C[ P[j] ]) G = C[ P[ i ] ];
DP[ j ] = max(DP[ j-1 ] - (T[ P[ j ] ] - T[ P[ j-1 ] ])*M + G, G - M);
if(DP[ j ] > profMax ) profMax = DP[ j ];
}
}
fprintf(fout, "%ld\n", profMax);
}
int main()
{
readData();
sort(P+1, P+N+1, cmp);
solve();
fclose(fin);
fclose(fout);
return 0;
}