Cod sursa(job #536992)

Utilizator razyelxrazyelx razyelx Data 19 februarie 2011 20:51:12
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream.h>
#include <algorithm>
#define N 2001

using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

struct C{
	int t;
	long long p;
} client[N];

long long n,c,best = -(1<<64);

void read(){
	int i;
	
	fin>>n>>c;
	
	for (i=1; i<=n; i++)
		fin>>client[i].t>>client[i].p;

}
int cmp(C x, C y){
	return x.t < y.t;
}

void fixeaza(int start, int stop, int newP, long long &pfixat, long long &max){

	int i,sum1=0;
	
	if ( client[start].p >= newP)
		sum1 += newP - c;
	else
		sum1 -= c;
		
	
	for (i=start+1; i<=stop; i++)
		if ( client[i].p >= newP)
			sum1 += newP - (client[i].t-client[i-1].t)*c;
		else
			sum1 -= (client[i].t-client[i-1].t)*c;
	
			
	if (newP >= pfixat)
		max += pfixat - (client[stop].t - client[stop-1].t) * c;
	else
		max -= (client[stop].t - client[stop-1].t) * c;
		
	if (sum1 > max){
		max = sum1;
		pfixat = newP;
	}
		

}

void solve(){
	int i,startIdx=1;
	long long pfixat = 1<<64,max = -(1<<64);
	
	//max = client[1].p - c;	
	//pfixat = client[1].p;
	
	for (i=1; i<=n; i++){
		
		if (max > best) best = max;
		
		fixeaza(startIdx,i,client[i].p,pfixat,max);
		
		// if vechea suma calculata cu pretul nou este mai mica decat elementul curent
		// atunci noua secventa incepe de la elementul curent
		// altfel se adauga elementu curent a noua suma.

		if ( max < client[i].p - c){
			max = client[i].p - c;
			startIdx = i;
		}
			
		
	
	}
}


int main(){
	
	read();
	sort(client,client+n,cmp);
	solve();
	
	/*for (int i=1; i<=n;  i++)
		fout<<client[i].t<<" ";*/
	
	fout<<best;
	
	return 0;
}