Cod sursa(job #1174038)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 21 aprilie 2014 19:11:07
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#include<algorithm>
using namespace std;


long int p[2010],c,pret;
int t[2010],n;

int main(){
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d%ld",&n,&c);
	for(int i=1;i<=n;i++){
		scanf("%d%ld",&t[i],&p[i]);
	}
  long	int sol = -100000000,sum,poz,old,news,G;
/*	for(int i=1;i<=n;i++){
	   poz = 1;
	   sum=0;
	   if(p[i]-c>sol)sol=p[i]-c;
	   for(int j=1;j<=n;j++){
	   	if(p[i]<=p[j])sum+=p[i];
		sol=max(sol,sum-(t[j]-t[poz]+1)*c);
		if(sum-(t[j]-t[poz]+1)*c<0)sum=0,poz=j+1;
	   	
	   }
	}*/
	for(int i=1;i<=n;i++){
		old=0;
		for(int j=1;j<=n;j++){
			if(p[j]>=p[i])G=p[i];else G=0;
			news = old - (t[j]-t[j-1])*c+G;
			if(G-c>news)news=G-c;
			if(news>sol)sol=news;
			old=news;
		}
		
	}
	printf("%ld",sol);
}