Cod sursa(job #1173408)

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

long long a[2000],at[2000];
long p[2000],c,pret;
int t[2000],n;

int main(){
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d%d",&n,&c);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&t[i],&p[i]);
	}
	long long sol = -100000000,sum,poz;
	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;
	   }
	}
	printf("%d",sol);
}