Cod sursa(job #138848)

Utilizator andrei.12Andrei Parvu andrei.12 Data 19 februarie 2008 12:46:54
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h> 
#include<algorithm>

using namespace std;

#define lg 2005
#define pretmax 1000000000

int n, c, i, raspuns;
struct ches{
	int t, c;
};
ches v[lg];
inline int cmp(ches a, ches b){
	return (a.t < b.t);
}
void check(int val){
	int i, st = 0, rz = 0, fs = 0;
	
	st = v[1].t-1;
	for (i = 1; i <= n; i ++){
		if (val <= v[i].c)
			rz += val;
		else
			fs = 1;
	
		rz -= c*(v[i].t - st);
		//printf("%d\n", rz);
		if (rz > raspuns)
			raspuns = rz;
		st = v[i].t;

		if (rz < 0)
			rz = 0, st = v[i+1].t-1;

		//printf("%d %d\n\n", rz, st);
	}
	
}
void find(){
	int i;

	for (i = 1; i <= n; i ++)
		check(v[i].c);
}
int main()
{
	freopen("carnati.in", "rt", stdin);
	freopen("carnati.out", "wt", stdout);

	scanf("%d%d", &n, &c);
	for (i = 1; i <= n; i ++)
		scanf("%d%d", &v[i].t, &v[i].c);
		
	sort(v+1, v+n+1, cmp);

	find();
	
	printf("%d\n", raspuns);

	return 0;
}