Cod sursa(job #1601049)

Utilizator Bodo171Bogdan Pop Bodo171 Data 15 februarie 2016 18:06:37
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int i,n,j,best[100000],p,u,m,key;
struct formatie{int a,b;}v[100000];
bool compare(formatie x,formatie y)
{
    if(x.a==y.a) return x.b<y.b;
    return x.a<y.a;
}
int main()
{
f>>n;
for(i=1;i<=n;i++) f>>v[i].a>>v[i].b;
sort(v+1,v+n+1,compare);
for(i=1;i<=n;i++)
{
    if(v[i].b-v[i].a>best[i]) best[i]=v[i].b-v[i].a;
    if(best[i-1]>best[i]) best[i]=best[i-1];
    key=v[i].b;p=i;u=n;
    while(p<u)
    {
        m=(p+u)/2;
        if(v[m].a<key) p=m+1;
        else u=m;
    }
    m=(p+u)/2;
    if(v[m].a<key) m++;
    j=m;
    while(j<=n) {
    if(best[i]+v[j].b-v[j].a>best[j])
        best[j]=best[i]+v[j].b-v[j].a;j++;}

}

g<<best[n];
f.close();
g.close();
    return 0;
}