Cod sursa(job #1220260)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 16 august 2014 23:53:54
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

#define NMAX 2001

struct entry {
	int timp,bani;
};

struct cmp {
	bool operator () (const entry &a, const entry &b) {
		if(a.timp==b.timp)
			return a.bani<b.bani;
		return a.timp<b.timp;
	}
};

long long d[NMAX];
entry v[NMAX];

long long maxim(long long a, long long b)
{
	if(a>=b)
		return a;
	return b;
}

long long solve(int C, int pret, int n)
{
	int i,j;
	long long sol;
	d[1]=0LL+pret*(v[1].bani>=pret)-C;
	for(i=2;i<=n;i++) 
		d[i]=maxim(0LL+d[i-1]-1LL*(v[i].timp-v[i-1].timp)*C,-C)+pret*(v[i].bani>=pret);
	sol=0;
	for(i=1;i<=n;i++)
		sol=maxim(sol,d[i]);
	return sol;
}

int main ()
{
	int i,n,C;
	long long sol;
	ifstream f("carnati.in");
	ofstream g("carnati.out");
	f>>n>>C;
	for(i=1;i<=n;i++)
		f>>v[i].timp>>v[i].bani;
	f.close();
	sort(v+1,v+n+1,cmp());
	sol=0;
	for(i=1;i<=n;i++)
		sol=maxim(sol,solve(C,v[i].bani,n));
	g<<sol;
	g.close();
	return 0;
}