Cod sursa(job #945549)

Utilizator teoionescuIonescu Teodor teoionescu Data 2 mai 2013 11:35:44
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<fstream>
#include<algorithm>
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++) if(v[i].p>smax) smax=v[i].p;
	for(i=1;i<=n;i++){
		pret=v[i].p;
		s=0;
			if(v[1].p>=pret) aux=pret;
			else aux=0;
		s+=aux;
		for(j=2;j<=n;j++){
			aux=-(v[j].t-v[j-1].t)*C;
			s+=aux;
			if(s<0) s=0;
			if(v[j].p>=pret) aux=pret;
			else aux=0;
			s+=aux;
			if(s>smax) smax=s;
		}
	}
	out<<smax-C;
	return 0;
}