Cod sursa(job #142671)

Utilizator Matei14Popa-Matei Mihai Matei14 Data 24 februarie 2008 21:50:36
Problema Carnati Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#define N 2000
int n,i,j,p[N],t[N],c,min,max=0,a[1000],x,y,g,s[1000];
void sort(){
	for(i=0;i<n-1;++i){
		min=i;
		for(j=i+1;j<n;++j)
			if(t[j]<t[min])
				min=j;
		if(min!=i){
			x=t[i];
			t[i]=t[min];
			t[min]=x;
			x=p[i];
			p[i]=p[min];
			p[min]=x;
		}
	}
}
int maxim(int x,int y){
	if(x>y)
		return x;
	return y;
}
int main(){
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d%d",&n,&c);
	for(i=1;i<=n;++i)
		scanf("%d%d",&t[i],&p[i]);
	sort();
	for(j=1;j<=n;++j){
		a[0]=0;
		for(i=1;i<=n;++i){
			g=0;
			if(p[i]>=p[j])
				g=p[j];
			x=a[i-1]-(t[i]-t[i-1])*c+g;
			y=g-c;
			a[i]=maxim(x,y);
			if(a[i]>max)
				max=a[i];
		}
	}
	printf("%d\n",max);
	fclose(stdin);
	fclose(stdout);
	return 0;
}