Cod sursa(job #1853065)

Utilizator MarcSpataruMarc Spataru MarcSpataru Data 21 ianuarie 2017 13:37:48
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include<cstdio>
#include<algorithm>

using namespace std;

struct ura{
    int st,dr,timp;};

ura v[100001],stiva[100001];

bool sortare (ura a, ura b){
    if (a.st<b.st)
        return a.st<b.st;
    if (a.st==b.st)
        return a.dr<b.dr;
    return a.st<b.st;
    }

int main()

{

freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);

int n,i,j,pp=0;

scanf ("%d",&n);

for (i=1;i<=n;i++){
    scanf ("%d%d",&v[i].st,&v[i].dr);
    v[i].timp=v[i].dr-v[i].st;
}

sort (v+1,v+n+1,sortare);
int h=1,s,cate,ch;
stiva[1].st=v[1].st;
stiva[1].dr=v[1].dr;
stiva[1].timp=v[1].timp;
for(i=2;i<=n;i++)
{
    if(v[i].st>=stiva[h].dr)
    {
        stiva[++h].st=v[i].st;
        stiva[h].dr=v[i].dr;
        stiva[h].timp=v[i].timp;
    }
    else
    {
        cate=0;
        ch=h;
        s=0;
        //verificare
        while(v[i].st<stiva[ch].st||(v[i].st>=stiva[ch].st&&v[i].st<=stiva[ch].dr))
        {
            cate++;
            s+=stiva[ch].timp;
            ch--;
        }
        if(v[i].timp>s)
        {
            h=ch;
            stiva[++h].st=v[i].st;
            stiva[h].dr=v[i].dr;
            stiva[h].timp=v[i].timp;
        }
    }
}
s=0;
for(i=1;i<=h;i++)
    s+=stiva[i].timp;
printf("%d",s);
return 0;
}