Cod sursa(job #1366660)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 1 martie 2015 12:39:10
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100023
using namespace std;
FILE *fin, *fout;
int n, d[NMAX], pos, maxn;
struct concert
{
	int st;
	int dr;
} v[NMAX];
bool comp(concert a, concert b)
{
	if(a.st < b.st) return 1;
	if(a.st > b.st) return 0;
	if(a.dr < b.dr) return 1;
	return 0;
}
bool comp1(concert a, int b)
{
	return (a.dr <= b);
}
int main()
{
	fin = freopen("heavymetal.in", "r", stdin);
	fout = freopen("heavymetal.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i<= n; i++) scanf("%d%d", &v[i].st, &v[i].dr);
	sort(v+1, v+n+1, comp);
	d[1] = v[1].dr - v[1].st;
	d[0] = 0;
	v[0].st = 0;
	v[0].dr = 0;
	maxn = d[1];
	for(int i = 2; i<= n; i++)
	{
		pos = lower_bound(v+1, v+n+1, v[i].st, comp1) - v - 1;
		d[i] = v[i].dr - v[i].st + d[pos];
		if(d[i] > maxn) maxn = d[i];
	}
	printf("%d\n", maxn);
	//for(int i = 0; i<= n; i++) printf("%d ", d[i]);printf("\n");
	fclose(fin);
	fclose(fout);
	return 0;
}