Cod sursa(job #515532)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 21 decembrie 2010 17:49:08
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
const int N=2000;
int n,c,i,j,sum,smax,t;
ifstream aa("carnati.in");
ofstream ss("carnati.out");
struct aaa{
	int t,p;
};
aaa vec[N];
bool cmp(aaa x,aaa y) {
	return x.t<y.t;
}
int calc(int pret) {
	int sc=0,smax=-1000000000,i;
	for(i=1;i<=n;++i)
	{
		if(i>1)
			sc -= (vec[i].t - vec[i-1].t - 1) * c;
		if(sc < 0)
			sc = 0;
		if(vec[i].p >= pret)
			sc += pret;
		sc -= c;
		if(sc > smax)
			smax = sc;
	}
	return smax;
}
int main() {
	aa >> n >> c;
	for (i=1;i<=n;++i) {
		aa >> vec[i].t >> vec[i].p;
	}
	sort(&vec[1],&vec[n+1],cmp);
	for (i=1;i<=n;++i) {
		sum=calc(vec[i].p);
		if (sum>smax)
			smax=sum;
	}
	ss << smax;
	aa.close();
	ss.close();
	return 0;
}