Cod sursa(job #893853)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 26 februarie 2013 18:16:58
Problema Carnati Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

const char infile[] = "carnati.in";
const char outfile[] = "carnati.out";

#define MAXN 2001

int N, C;

struct Carnat
{
	int T;
	int P;
};

Carnat A[MAXN];


int Result = 0;


int cmp(const Carnat a, const Carnat b)
{
	return a.T <= b.T;
}


void citire()
{
	
	fstream fin(infile, ios::in);

	fin >> N >> C;

	for(int i = 0; i < N; i++)
	{
		fin >> A[i].T;
		fin >> A[i].P;
		
	}


	fin.close();

	sort(A, A+N, cmp);
}


int pd(int price)
{
	
	int profit = -1;
	int last = 0;
	for(int i = 0; i < N; i++)
	{

		if(profit == -1)
		{
			if(A[i].P >= price)
			{
				profit = price - C;
				last = A[i].T;
			}
		}
		else if(A[i].P < price)
		{
			continue;
		}
		else
		{
			if(profit < profit + price - (A[i].T - last)*C)
			{
				profit = profit + price - (A[i].T - last)*C;
				last = A[i].T;
			}
			if(profit < price - C)
			{
				profit = price - C;
				last = A[i].T;
			}
		}

	}
	return profit;
}


void solve()
{
	for(int i = 0; i < N; i++)
	{
		Result = max(Result, pd(A[i].P));
	}
}


void afisare()
{
	fstream fout(outfile, ios::out);
	fout << Result << "\n";
	fout.close();
}

int main()
{
	citire();
	solve();
	afisare();
}