Pagini recente » Cod sursa (job #1213251) | Cod sursa (job #3160558) | Cod sursa (job #647313) | Cod sursa (job #2708196) | Cod sursa (job #1904314)
#include <cstdio>
#include <algorithm>
using namespace std;
struct pair1
{
int in,sf;
}nr[100001];
struct pair2
{
int total,capat;
}v[100001];
char s[25];
int L;
bool cmp(const pair1 &a,const pair1 &b)
{
return a.sf<b.sf;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n;
scanf("%d ",&n);
for (int i=1;i<=n;++i)
{
gets(s);
bool a=0,a1=0,a2=0;
for (int j=0;s[j]!=0;++j)
{
if (s[j]==' ') a=1;
else
{
if (s[j]=='-' && a==0) a1=1;
else if (s[j]=='-' && a==1) a2=1;
else {
if (a==0) nr[i].in=nr[i].in*10+s[j]-'0';
else nr[i].sf=nr[i].sf*10+s[j]-'0';
}
}
}
if (a1==1) nr[i].in=-nr[i].in;
if (a2==1) nr[i].sf=-nr[i].sf;
}
sort(nr+1,nr+n+1,cmp);
for (int i=1;i<=n;++i)
{
int j=0,step=1;
for (;step<=L;step<<=1);
for (;step;step>>=1)
if (j+step<=L && v[j+step].capat<=nr[i].in)
j+=step;
if (v[j].total+(nr[i].sf-nr[i].in)>v[L].total)
{
++L;
v[L].capat=nr[i].sf;
v[L].total=v[j].total+(nr[i].sf-nr[i].in);
}
}
printf("%d",v[L].total);
}