Cod sursa(job #893956)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 26 februarie 2013 18:57:08
Problema Carnati Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 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 = 0;
	int last = -7;
	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;
		}

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