Cod sursa(job #898552)

Utilizator superman_01Avramescu Cristian superman_01 Data 28 februarie 2013 10:40:32
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>

#define MAX_SIZE 2005

FILE *f=fopen("carnati.in","r");
FILE *g=fopen("carnati.out","w");

using namespace std;

 vector < pair< int,int> >  v;
int n,x,y,cost;
int bst;

void read ( void )
{
	
	fscanf(f,"%d%d",&n,&cost);
	
	for(int i(1); i <= n ; ++i )
	{
	   fscanf(f,"%d%d",&x,&y);
	   v.push_back(make_pair(x,y));	
	}
	fclose(f);
}



void solve( void )
{
	int price,S;
	sort(v.begin(),v.end());
	
	for(int i(0); i <  n ; ++i )
	{
		
		price=v[i].second;
		
		if(price <= v[0].second )
		{
			S=price-cost;
			if(S>bst)
				bst=S;
		}
		else
			S=-cost;
		
		for(int ii(1); ii < n ; ++ii )
		{
			S-=(v[ii].first-v[ii-1].first-1)*cost;
			
			
			if(S < 0 )
				S=0;
			
			
			if(price <= v[ii].second ) 
			      S+=price;
			
			S-=cost;
			if(S>bst)
				bst=S;
			
		
		}
		
	}
	
	
}
void write ( void )
{
	
	fprintf(g,"%d",bst);
}


int main( void )
{
	read();
	solve();
	write();
    return 0;	
}