Cod sursa(job #2150156)

Utilizator BotzkiBotzki Botzki Data 3 martie 2018 12:06:21
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX=10000;
int d[NMAX+5];
struct timp
{
    int inc, sf;
};
timp v[NMAX+5];
bool cmp(timp a, timp b)
{
    if(a.sf==b.sf)
    {
        return a.inc<=b.inc;
    }
    else
        return a.sf<=b.sf;
}
int main()
{
   int n, i, tc, st, dr, mid;
   fin>>n;
   for(i=1;i<=n;i++)
      fin>>v[i].inc>>v[i].sf;
   sort(v+1,v+n+1, cmp);
   d[1]=v[1].sf-v[1].inc;
   for(i=2;i<=n;i++)
   {
      tc=v[i].inc;
      st=1;
      dr=i-1;
      while(st<=dr)
      {
          mid=(st+dr)/2;
          if(v[mid].sf<=tc)
            st=mid+1;
          else
            dr=mid-1;
      }
      d[i]=max(v[i].sf-v[i].inc+d[dr], d[i-1]);
   }
   fout<<d[n]<<"\n";
    return 0;
}