Cod sursa(job #945546)

Utilizator teoionescuIonescu Teodor teoionescu Data 2 mai 2013 11:31:05
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");
const int N = 2005;
struct carnat{
	int t,p;
};
carnat v[N];
int n,C,pret,aux,s,smax;
bool cmp(carnat a,carnat b){
	return a.t<b.t;
}
int main(){
	int i,j;
	in>>n>>C;
	for(i=1;i<=n;i++) in>>v[i].t>>v[i].p;
	sort(&v[1],&v[n+1],cmp);
	//for(i=1;i<=n;i++) out<<v[i].t<<' '<<v[i].p<<'\n';
	for(i=1;i<=n;i++){
		pret=v[i].p;
		//out<<"   :"<<pret<<'\n';
		s=0;
			if(v[1].p>=pret) aux=pret;
			else aux=0;
		s+=aux;
		//out<<s<<'\n';
		for(j=2;j<=n;j++){
			aux=-(v[j].t-v[j-1].t)*C;
			s+=aux;
			if(s<0) s=0;
			//out<<aux<<' ';
			if(v[j].p>=pret) aux=pret;
			else aux=0;
			s+=aux;
			//out<<aux<<' ';
			//out<<"     "<<s<<'\n';
			if(s>smax) smax=s;
		}
	}
	out<<smax-C;
	return 0;
}