Cod sursa(job #137830)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 17 februarie 2008 15:07:27
Problema Heavy metal Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long n, o, nr1, nr2, i, max, sumcur, f[100010];

struct mystruct {
	long timp;
	long stare;
	long interval;
	long dist;
};

mystruct v[200010];

int cmp(const void *a, const void *b) {
	mystruct c = *(mystruct *)a, d = *(mystruct *)b;
	if (c.timp != d.timp) {
		return c.timp - d.timp;
	} else {
		return -(c.stare - d.stare);
	}
}

int main() {
	freopen("heavymetal.in", "r", stdin);
	freopen("heavymetal.out", "w", stdout);
	scanf("%ld", &n);
	o = 0;
	for (i = 1; i <= n; ++i) {
		scanf("%ld %ld", &nr1, &nr2);
		++o;
		v[o].timp = nr1;
		v[o].stare = 0;
		v[o].interval = i;
		v[o].dist = nr2 - nr1;
		++o;
		v[o].timp = nr2;
		v[o].stare = 1;
		v[o].interval = i;
		v[o].dist = nr2 - nr1;
	}
	
	qsort(v + 1, o, sizeof(v[0]), cmp);
	/*for (i = 1; i <= o; ++i) {
		printf("%ld %ld %ld\n", v[i].timp, v[i].stare, v[i].interval);
	}*/
	for (i = 1; i <= o; ++i) {
		if (v[i].stare == 0) {
			
			f[v[i].interval] = max + v[i].dist;
		} else {
			if (max < f[v[i].interval]) {
				max = f[v[i].interval];
			}
		}
	}
	printf("%ld\n", max);
	return 0;
}