Cod sursa(job #206226)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 5 septembrie 2008 13:36:33
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

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

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

vector < mystruct> v(200010);

bool cmp(mystruct c, mystruct d) {
	
	if( c.timp < d.timp)
		return true;
	if( c.timp == d.timp && c.stare> d.stare)
		return true;
	return false;
	
}

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;
	}
	
	sort( v.begin()+1, v.begin() + o + 1,cmp);
	//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] = max1 + v[i].dist;
		} else {
			if (max1 < f[v[i].interval]) {
				max1 = f[v[i].interval];
			}
		}
	}
	printf("%ld\n", max1);
	return 0;
}