Cod sursa(job #2553852)

Utilizator mihaiailincai1Mihai Ailincai mihaiailincai1 Data 22 februarie 2020 12:27:23
Problema Heavy metal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb

#include <iostream>

#include<fstream>

#include<algorithm>

#define N 100005

using namespace std;

ifstream fin("heavymetal.in");

ofstream fout("heavymetal.out");



struct pereche

{

    int x,y;

};



pereche a[N];

int lg[N];

int n;



int compara(int i,int j)
{

    if(a[i].y>a[j].y)return 1;

    if(a[i].y==a[j].y&&a[i].x>a[j].x)return 1;
    return 0;

}



int pivotare(int s,int d)

{

    int pasi=0,pasj=1,i=s,j=d;

    int p=s+rand()%(d-s+1);

    pereche aux=a[s];a[s]=a[p];a[p]=aux;



    while(i<j)

    {

        if(compara(i,j)==1)

        {

            aux=a[i];a[i]=a[j];a[j]=aux;

            pasi=1-pasi;

            pasj=1-pasj;

        }

        i+=pasi;

        j-=pasj;

    }

    return i;

}



void qs(int s,int d)

{

    if(s<d)

    {

        int p=pivotare(s,d);

        qs(s,p-1);

        qs(p+1,d);

    }

}



void bubblesort()

{

    int i;

    pereche aux;

    bool ordo=false;

    while(ordo=false)

    {

    ordo=true;

    for(i=1;i<n;++i)

        if(compara(i,i+1)==1)

    {

        ordo=false;

        aux=a[i];a[i]=a[i+1];a[i+1]=aux;

    }

    }

}





void solve()

{

    int i,j,lgmax=0,timp;

    for(i=1;i<=n;++i)

    {

        lg[i]=a[i].y-a[i].x;
        timp=lg[i];

        for(j=1;j<i;++j)

            if(a[j].y<=a[i].x&&lg[j]+timp>lg[i])
        {

            cout<<a[j].y<<" "<<a[i].x<<"\n";

            lg[i]=lg[j]+timp;

            if(lg[i]>lgmax)lgmax=lg[i];
        }

    }

    fout<<lgmax;





}



void print()

{

    int i;

    for(i=1;i<=n;++i)



        fout<<a[i].x<<" "<<a[i].y<<"\n";

}



int main()



{

    int i;

    fin>>n;

    for(i=1;i<=n;++i)

        fin>>a[i].x>>a[i].y;

    qs(1,n);


    solve();





    return 0;

}