Cod sursa(job #1857094)

Utilizator Cezar_MihalceaCezar Mihalcea Cezar_Mihalcea Data 25 ianuarie 2017 20:07:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<fstream>
using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

struct spec
{
	int inc,sf;
};

spec v[100001];
int n,sol[100001];

int bs(int x)
{
	int pas = 1<<16,i=0,j;
	while(pas)
	{
		if(i+pas<=n && v[i+pas].sf<=v[x].inc)
			i+=pas;
		pas/=2;
	}
	return i;
}

void schimb(spec &a,spec &b)
{
    spec aux;
    aux=a;
    a=b;
    b=aux;
}

int partitie(int st,int dr)
{
    int i,j;
    j=st;
    for(i=st;i<dr;i++)
    {
        if(v[i].sf<v[dr].sf)
            schimb(v[j++],v[i]);
    }
    schimb(v[j],v[dr]);
    return j;
}

void qsort(int st,int dr)
{
    if(st>=dr)
        return;
    int p=partitie(st,dr);
    qsort(st,p-1);
    qsort(p+1,dr);
}

int maxim(int a,int b)
{
	if(a>b)
		return a;
	return b;
}

int main()
{
	int i,maxx=0,j;
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i].inc>>v[i].sf;
	qsort(1,n);
	for(i=1;i<=n;i++)
		if(v[i].sf - v[i].inc > maxx)
		{
			maxx = v[i].sf - v[i].inc;
			sol[i] = maxx;
		}
		else
			sol[i] = maxx;
	for(i=2;i<=n;i++)
	{
		j = bs(i);
		sol[i] = maxim(sol[i-1], sol[j] + (v[i].sf - v[i].inc));
	}
	g<<sol[n];
	return 0;
}