Cod sursa(job #502201)

Utilizator osiceanu_paulOsiceanu paul osiceanu_paul Data 18 noiembrie 2010 12:01:09
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

const int N=1<<16;
struct punct
{
	int t,p;
};
punct v[N];
bool cmp(punct p , punct q)
{
	return p.t<q.t;
}

int n,c;

int calcul(int pret)//calc cel mai mare castig pe care-l poate obtine daca fixeaza pretul de vanzare = pret
{
	int sc=0,smax=-1000000000,i;
	for(i=1;i<=n;++i)
	{
		if(i>1)
			sc -= (v[i].t - v[i-1].t - 1) * c;
		if(sc < 0)
			sc = 0;
		if(v[i].p >= pret)
			sc += pret;
		sc -= c;
		if(sc > smax)
			smax = sc;
	}
	return smax;
}

int main()
{
	int i,s,smax=-1;
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d %d",&n,&c);
	for(i=1;i<=n;++i)
		scanf("%d %d",&v[i].t,&v[i].p);
	sort(&v[1],&v[n+1],cmp);
	for(i=1;i<=n;++i)
	{
		s = calcul(v[i].p);
		if(s>smax)
			smax=s;
	}		
	
	printf("%d",smax);
}