Cod sursa(job #1667953)

Utilizator murgoci1Gheorghe Murgoci murgoci1 Data 29 martie 2016 13:27:39
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,max0,i,j,max1;
struct trup{
    int s;
    int e;
    int d;
    }trupe[100005];
bool comp(trup i,trup j)
{
    return i.s<j.s || (i.s==j.s && i.e<j.e);
}
int main()
{   int i;
   fin>>n;
   for(i=1;i<=n;i++)
   {
       fin>>trupe[i].s;
       fin>>trupe[i].e;
       trupe[i].d=0;

   }
   sort(trupe,trupe+n+1,comp);
    trupe[1].d=trupe[1].e-trupe[1].s;
    max0=trupe[1].d;
    for(i=2;i<=n;i++){
        max1=0;
        for(j=i;j>=1;j--)
            if (trupe[i].s>=trupe[j].e && trupe[j].d>max1)
            {
                max1=trupe[j].d;
                break;}
        trupe[i].d=(trupe[i].e-trupe[i].s)+max1;
        if(trupe[i].d>max0)max0=trupe[i].d;
    }
    fout<<max0;
    fin.close();
    fout.close();
    return 0;
}