Cod sursa(job #2540544)

Utilizator eusebiu_alexandruMorar Eusebiu eusebiu_alexandru Data 7 februarie 2020 12:23:07
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb

#include<fstream>
#include<algorithm>
#define nmax 100007

using namespace std;
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
struct ana
{
    int x,y;
}v[nmax];
bool cmp(ana a,ana b)
{
    if(a.y!=b.y)
         return a.y<b.y;
    return a.x<b.x;
}
int sol[nmax],n,i,jm,st,dr,mij,rezultat;
int main()
{
f>>n;
for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;
 sort(v+1,v+n+1,cmp);
 sol[1]=v[1].y-v[1].x;
 for(i=2;i<=n;i++)
 {
      sol[i]=sol[i-1]; /// nu il pun
      st=1,dr=i-1;
      rezultat=0;
      mij=(st+dr)/2;
      while(st<=dr)
      {
         if(v[mij].y<=v[i].x)
         {
          rezultat=mij;
          st=mij+1;
         }
         else
            dr=mij-1;
         mij=(st+dr)/2;
      }
     sol[i]=max(sol[i-1],sol[mij]+v[i].y-v[i].x);
 }
 g<<sol[n];
}