Cod sursa(job #139138)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 19 februarie 2008 19:19:25
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const long MAX=100000;
struct p { 
	long st, dr;
} A[MAX], X;
int comp(p A, p B) { return (A.dr-A.st)<(B.dr-B.st); }
long n,i, ans;

int main() {
	freopen("heavymetal.in", "r", stdin);
	scanf("%ld", &n);
	for (i=0; i<n; ++i)
		scanf("%ld %ld", &A[i].st, &A[i].dr);
	fclose(stdin);

	sort(A, A+n, comp);
	X = A[n-1]; ans = X.dr-X.st;
	for (i=n-2; i+1; --i) {
		if ( A[i].dr<=X.st ) {
			ans += A[i].dr-A[i].st;
			X.st = A[i].st;
		}
		if ( A[i].st>=X.dr ) {
			ans += A[i].dr - A[i].st;
			X.dr = A[i].dr;
		}
	}

	fprintf(fopen("heavymetal.out", "w"), "%ld\n", ans);
	return 0;
}