Cod sursa(job #3224290)

Utilizator theo_aldescuTheodora Aldescu theo_aldescu Data 15 aprilie 2024 08:50:20
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct timp 
{int st,dr;
}a[100005];
int comp(timp x,timp b)
{return x.dr<b.dr;
}
int n,i,p,u,sol,mij,j;
long long v[100005];
int main()
{f>>n;
for(i=1;i<=n;i++)f>>a[i].st>>a[i].dr;
sort (a+1,a+n+1,comp);
v[1]=a[1].dr-a[1].st;
for(i=2;i<=n;i++)
   {p=1;
   u=i;
   sol=0;
    while(p<=u) 
    {mij=(p+u)/2;
    if(a[i].st>=a[mij].dr) p=mij+1,sol=mij;
    else u=mij-1;
    }
    v[i]=max(v[i-1],a[i].dr-a[i].st+v[sol]);
    }
g<<v[n];
}