Cod sursa(job #517610)

Utilizator diehardNasturel Gabriel diehard Data 29 decembrie 2010 12:53:51
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<fstream>
using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

struct om{
	int t,p;
};

om v[2001];
int c,n;

void poz(int st,int dr,int &p){
	int i=st,j=dr,d=0;
	om aux;
	while(i<j){
		if(v[i].t>v[j].t){
			aux=v[i];
			v[i]=v[j];
			v[j]=aux;
			d=1-d;
		}
		
		i+=d;
		j-=1-d;
	}
	p=i;
}

void quicky(int st,int dr){
	int p;
	if(st<dr){poz(st,dr,p);
	quicky(st,p-1);
	quicky(p+1,dr);
	}
}




inline int profit(int p){
	int sc=0,prof=INT_MIN,i,u=-1;
	for(i=1;i<=n;i++){
		if(v[i].p<p)
			continue;
		if(u!=-1&&sc-(v[i].t-u-1)*c>0)
			sc+=p-(v[i].t-u)*c;
		else
			sc=p-c;
		if(sc>prof)
			prof=sc;
		u=v[i].t;
	}	
	return prof;

}
int main(){
	int i,nr,profmax=INT_MIN;
	fin>>n>>c;
	for(i=1;i<=n;i++)
	fin>>v[i].t>>v[i].p;
	//quicky(1,n);
	for(i=1;i<=n;i++)
		if(profit(v[i].p)>profmax)
			profmax=profit(v[i].p);
		
	fout<<profmax;
		
return 0;
}