Cod sursa(job #1904314)

Utilizator MelacasKorian Ebraahim Melacas Data 5 martie 2017 14:23:39
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#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);
}