Cod sursa(job #596049)

Utilizator Smaug-Andrei C. Smaug- Data 15 iunie 2011 17:58:55
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;

#define MAXN 2010
#define LOW -(1<<30)

int main(){

  freopen("carnati.in", "r", stdin);
  freopen("carnati.out", "w", stdout);

  int N, C, i, maxs, sum, j;
  pair<int,int> P[MAXN];

  scanf("%d%d", &N, &C);
  for(i=1; i<=N; i++)
    scanf("%d%d", &P[i].first, &P[i].second);

  sort(P+1, P+N+1);

  maxs=LOW;

  P[0].second=P[1].second-1;

  for(i=1; i<=N; i++){
    sum=0;
    
    for(j=1; j<=N; j++){
      if(P[j].second >= P[i].second){
	sum=max(sum-(P[j].first-P[j-1].first)*C+P[i].second, P[i].second-C);
	if(sum > maxs)
	  maxs=sum;
      }
      else
	sum=sum-(P[j].first-P[j-1].first)*C;
    }
    
  }

  printf("%d\n", maxs);

  return 0;

}