Cod sursa(job #368527)

Utilizator adrian_manducadrian manduc adrian_manduc Data 25 noiembrie 2009 09:58:30
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct carnat
{
	int t,p;
};
carnat a[1<<11];
int cpmax=0;
int prdmax(int p,int c,int n)
{
	int j,sc,smax=0;
	if(a[1].p>=p)
		sc=sc-c;
	else
		sc=0;
	for(j=1; j<=n; j++)
	{
		sc=sc-c*(a[j].t-a[j-1].t-1);
		if(sc<0)
			sc=0;
		if(p<=a[j].p)
			sc=sc+p;
		sc-=c;
		if (sc>smax)
			smax=sc;
	}
	return smax;
}
bool comp(const carnat &x, const carnat &y)
{
	return x.t<y.t;
}
int main()
{
	ifstream f("carnati.in");
	ofstream g("carnati.out");
	int prmax,i,n,c,p;
	f>>n; f>>c;
	for(i=1; i<=n; i++)
	{
		f>>a[i].t;
		f>>a[i].p;
	}
	sort(a+1,a+n+1,comp);
	prmax=0;
	for(i=1; i<=n; i++)
	{
		p=a[i].p;
		cpmax=prdmax(a[i].p,c,n);
		if( cpmax>prmax)
			prmax=cpmax;
	}
	g<<cpmax;
	return 0;
}