Cod sursa(job #852796)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 11 ianuarie 2013 19:04:02
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<fstream>

using namespace std;


ifstream f("carnati.in");
ofstream g("carnati.out");
struct cub {
	int t,p;
}v[2010];
int A[2010];
int i,j,pret,profit,C,n;
int cmp(cub a,cub b){
	return a.t<b.t;
}
inline int max(int a,int b){
	if(a>b)
		return a;
	return b;
}
int main () {
	
	f>>n>>C;
	v[0].t=v[0].p=-1;
	for(i=1;i<=n;++i){
		f>>v[i].t>>v[i].p;
	}
	sort(v+1,v+1+n,cmp);
	for(i=1;i<=n;++i){
		pret=v[i].p;
		int g;
        for(int j = 1;j<=n;j++){
          
			if(pret<=v[j].p)
				g=pret;
			else
				g=0;
            A[j]=max(A[j - 1]-(v[j].t-v[j-1].t)*C+g,g-C);
            profit=max(A[j],profit);
        }
	}
	g<<profit<<"\n";
	return 0;
}