Cod sursa(job #540601)

Utilizator slycerdan dragomir slycer Data 24 februarie 2011 09:10:54
Problema Carnati Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <stdlib.h>
struct om{
	int timp; 
	int pretMaxim; 
};

FILE * in = NULL; 
FILE * out = NULL; 
struct om * data; 
long * aux; 
int salariuPeOra; 
int n; 

long getValue(int i,int pret){
	
	int delta = 1;
	if ( i>=1){
		delta = data[i].timp-data[i-1].timp;
	}
	
	if ( pret <= data[i].pretMaxim ){
		return pret-salariuPeOra*delta; 
	} else {
		return -salariuPeOra*delta; 
	}
}

long profit_maxim( int pret  ){
	int i; 
	long max = -1 * (1<<18);
	aux[0] = getValue(0,pret);
	for ( i=1; i<n; i++){
		long cv = getValue(i,pret); 
		//printf("%d\n",cv);
		
		long k = pret<=data[i].pretMaxim?pret-salariuPeOra:-salariuPeOra;
		
		if ( k>aux[i-1]+cv){
			aux[i] = k; 
		} else{
			aux[i] = aux[i-1]+cv;
		}
		if ( aux[i]>max){
			max = aux[i]; 
		}
	}
	return max; 
}



int main()
{
	
	in = fopen("carnati.in","r");
	out = fopen("carnati.out","w"); 
	
	fscanf(in,"%d%d",&n,&salariuPeOra);
	data = calloc(n,sizeof(struct om)); 
	aux = calloc(n,sizeof(long)); 
	
	int i; 
	for ( i=0; i<n; i++){
		fscanf(in,"%d%d",&data[i].timp,&data[i].pretMaxim);
	}
	long max = profit_maxim(data[0].pretMaxim);
	long pret = data[0].pretMaxim; 
	//printf("Profit:%ld Pret:%ld\n",max,data[0].pretMaxim); 
	for ( i=1; i<n; i++){
		long cv = profit_maxim( data[i].pretMaxim);
	//	printf("Profit:%ld Pret:%ld\n",cv,data[i].pretMaxim); 
		if ( cv>max){
			max = cv; 
			pret = data[i].pretMaxim;
		}
	}
	
	//printf("%ld",pret);
	
	fprintf(out,"%ld",max);
	
	fclose( in ); 
	fclose( out ); 
	return 0; 
}