Pagini recente » Cod sursa (job #2701074) | Cod sursa (job #2522128) | Cod sursa (job #626112) | Cod sursa (job #2363961) | Cod sursa (job #586712)
Cod sursa(job #586712)
#include <iostream>
#include <fstream>
using namespace std;
int n,x,y,i,j,p,k,maxc;
int a[100000],b[100000],c[100000];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
void poz(int li,int ls,int&k)
{
int i=li,j=ls,c,i1=0,j1=-1;
while(i<j)
{
if(a[i]>a[j]||(a[i]==a[j]&&b[i]>b[j]))
{
swap (a[i],a[j]);swap (b[i],b[j]);
c=i1; i1=-j1; j1=-c;
}
i=i+i1; j=j+j1;
}
k=i;
}
void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls,k); quick(li,k-1); quick(k+1,ls);
}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>a[i]>>b[i];
quick (1,n);
c[1]=b[1]-a[1];
for (i=2;i<=n;i++)
{
maxc=0;
for (j=i;j>=1;j--)
if (a[i]>=b[j]&&c[j]>maxc) maxc=c[j];
c[i]=c[i]+maxc+b[i]-a[i];
}
maxc=0;
for (i=1;i<=n;i++)
if (c[i]>maxc) maxc=c[i];
g<<maxc;
f.close();
g.close();
return 0;
}
/*#include <iostream>
#include <fstream>
using namespace std;
int n,x,y,i,j,p,k,maxc;
int a[100000],b[100000],c[100000];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>a[i]>>b[i];
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
{
if (a[i]>a[j]) {swap(a[i],a[j]);swap(b[i],b[j]);}
if (a[i]==a[j])
if (b[i]>b[j]) swap (b[i],b[j]);
}
c[1]=b[1]-a[1];
for (i=2;i<=n;i++)
{
maxc=0;
for (j=i;j>=1;j--)
if (a[i]>=b[j]&&c[j]>maxc) maxc=c[j];
c[i]=c[i]+maxc+b[i]-a[i];
}
maxc=0;
for (i=1;i<=n;i++)
if (c[i]>maxc) maxc=c[i];
g<<maxc;
f.close();
g.close();
return 0;
}
*/