Cod sursa(job #347267)

Utilizator RobybrasovRobert Hangu Robybrasov Data 11 septembrie 2009 17:36:44
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#include <algorithm>
#define N 100000

using namespace std;

struct bands
{
    int li,ls;
} A[N];

int ind[N],timp[N],B[N];
//long long B[N];

bool cmp(int i, int j)
{
    /*if (A[i].li==A[j].li) return A[i].ls<A[j].ls;
    else return A[i].li<A[j].li;*/
    return A[i].ls<A[j].ls;
}

int main()
{
    int n,i,j,best,best_total=0;
    //long long best, best_total=0;
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	for (i=1; i<=n; i++) scanf("%d%d",&A[i].li,&A[i].ls), ind[i]=i, timp[i]=A[i].ls-A[i].li;

	sort(ind+1,ind+n+1,cmp);

    B[1]=timp[ind[1]];
    best_total=timp[ind[1]];
	for (i=2; i<=n; i++)
    {
        best=0;
        for (j=1; j<i; j++)
            if (A[ind[i]].li>=A[ind[j]].ls && A[ind[i]].ls>A[ind[j]].ls && B[j]+timp[ind[i]]>best)
                best=B[j]+timp[ind[i]];

        if (best>best_total) best_total=best;

        B[i]=best;
    }

    printf("%d",best_total);

    //for (i=1; i<=n; i++) printf("%d %d %d\n",A[ind[i]].li,A[ind[i]].ls,timp[ind[i]]);

	return 0;
}