Cod sursa(job #307497)

Utilizator CezarMocanCezar Mocan CezarMocan Data 24 aprilie 2009 11:37:23
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>
#include <algorithm>
#define maxn 2010

using namespace std;

struct carnat {
	int t, c;
};

int n, i, j, sol, cs, curr, mx, p, x;
int cat_scad, start;
carnat v[maxn];

bool cmp(carnat a, carnat b) {
	if (a.t < b.t)
		return true;
	return false;
}

int main() {
	freopen("carnati.in", "r", stdin);
	freopen("carnati.out", "w", stdout);

	scanf("%d%d", &n, &x);

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

	sort(v + 1, v + n + 1, cmp);
	v[0] = v[1];

	for (i = 1; i <= n; i++) {
		p = v[i].c;
//		printf("%d\n", p);
		cat_scad = 0;
		start = 1;

		cs = p;
		if (v[1].c < p)
			cs = 0;
		cs -= x;
		if (cs > sol)
			sol = cs;

		for (j = 2; j <= n; j++) {
			curr = p;
			if (v[j].c < curr)
				curr = 0;
			cat_scad = (v[j].t - v[j - 1].t) * x;
//			curr -= cat_scad;

			if (i == 3) {
//				printf("%d   %d    %d  %d\n", j, cs + curr - cat_scad, curr - x, start);
			}

			if (cs + curr - cat_scad > curr - x)
				cs = cs + curr - cat_scad;
			else {
				cs = curr - x;
				start = j;
			}

/*			if (i == 4)
				printf("%d %d\n\n", j, cs);*/

			if (cs > sol)
				sol = cs;
			cat_scad = (v[j + 1].t - v[j].t) * x;
		}
	}

	printf("%d\n", sol);

	return 0;
}