Cod sursa(job #894156)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 26 februarie 2013 20:01:10
Problema Carnati Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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 best = 0;
	int profit = 0;
	int last = -100;
	for(int i = 0; i < N; i++)
	{
		if(A[i].P < price)
			continue;

		if(0 < price - (A[i].T - last)*C)
		{
			profit += price - (A[i].T - last)*C;
			last = A[i].T;
		}
		else 
		{
			profit = price - C;
			last = A[i].T;
		}
		
		if(best < profit)
		{
			best = profit;
		}
	}
	return best;
}


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();
}