Cod sursa(job #2561846)

Utilizator andreitabaraandrei2004 andreitabara Data 29 februarie 2020 10:39:35
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct kys {int x,y;};
kys v[100002];
long long n,i,s[100002],j,cmax;
int comp (kys a,kys b)
{
    return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
int cb (int dr,int p)
{
    int st=1,mid;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid].y<=p){st=mid+1;}
        else{dr=mid-1;}
    }
    return st-1;
}

ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
int main()
{
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,comp);
    s[1]=v[1].y-v[1].x;
   for(i=2;i<=n;i++)
   {
    j=cb(i-1,v[i].x);
    if(s[i-1]>=s[j]+v[i].y-v[i].x)
    {
        s[i]=s[i-1];
    }
    else{s[i]=s[j]+v[i].y-v[i].x;}
   }

out<<s[n];
    return 0;
}