Cod sursa(job #368523)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 25 noiembrie 2009 09:50:06
Problema Carnati Scor 10
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");

struct carnat{
	int t;
	int p;
};

carnat v[1<<11];

int profmax(int p,int c,int n){
	int j,pc,pmaxp=0;
	if(v[1].p>=p)
		pc=p-c;
	else
		pc=0;
	for(j=2;j<=n;j++){
		pc=pc-c*(v[j].t-v[j-1].t-1);
		if(pc<0)
			pc=0;
		if(p<=v[j].p){
			pc=pc+p;
		}
		pc-=c;
		if(pc>pmaxp){
			pmaxp=pc;
		}
	}
	return pmaxp;
}

int main(){
	int n,c,i,p,pmax=0,ppmax;
	in>>n>>c;
	for(i=1;i<=n;i++){
		in>>v[i].t;
		in>>v[i].p;
	}
	for(i=1;i<=n;i++){
		p=v[i].p;
		ppmax=profmax(v[i].p,c,n);
		if(ppmax>pmax){
			pmax=ppmax;
		}
	}
	out<<pmax<<"\n";
	return 0;
}