Cod sursa(job #300518)

Utilizator alecmanAchim Ioan Alexandru alecman Data 7 aprilie 2009 14:47:32
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#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;
}