Pagini recente » Cod sursa (job #2915906) | Cod sursa (job #3156619) | Cod sursa (job #85960) | Cod sursa (job #2153100) | Cod sursa (job #2553852)
#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;
}