Cod sursa(job #1173404)

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

long long a[2000],at[2000];
long p[2000],c,pret;
int t[2000],n,k;
long long get_pret(){
	k=0;
	a[0]=0;
	for(int i=1;i<=n;i++){
		if(p[i]>=pret){
			k++;
			at[k]=(t[i]*c);
			a[k]=a[k-1]+pret;
				
			
		}
			
	}
	long long minim = -100000000;
	for(int i=k;i>1;i--)
	 for(int j=1;j<i;j++)minim=max(minim,a[i]-a[j-1]-(at[i]-at[j]+c));
//	printf("%d \n",minim);
//	for(int i=1;i<=k;i++)printf("%d ",a[i]);printf("\n");
//	for(int i=1;i<=k;i++)printf("%d ",at[i]);printf("\n");
//	for(int i=1;i<=k;i++)printf("%d ",a[i]-at[i]);
	
	return minim;
}
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]);
	//	printf("%d %d\n",t[i],p[i]);
	}
//	pret=p[4];
	long long sol = -100000000;
	for(int i=1;i<=n;i++){
		pret=p[i];
		sol = max(sol,get_pret());
	}
	printf("%d",sol);
//int v =	get_pret();
}