Cod sursa(job #1601032)

Utilizator Bodo171Bogdan Pop Bodo171 Data 15 februarie 2016 17:53:34
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int i,n,j,best[100000];
struct formatie{int a,b;}v[100000];
bool compare(formatie x,formatie y)
{
    if(x.b==y.b) return x.a<y.a;
    return x.b<y.b;
}
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];
    while(v[i].b>v[j].a&& j<=n) {j++;
    if(best[i]+v[j].b-v[j].a>best[j]) best[j]=best[i]+v[j].b-v[j].a;}

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