Cod sursa(job #916593)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 16 martie 2013 18:10:08
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct f
{
  short  int b,t;
}v[100005];
int n;
long maxx;
bool cmp(f c,f d)
{
    if(c.b!=d.b)
    return c.b<d.b;
    return c.t<d.t;
}
void bfs(long val,short int p)
{
    int i;
for(i=p+1;i<=n;i++)
{
if(v[i].b<v[i-1].t)
{
bfs(val+v[i].t-v[i].b-v[i-1].t+v[i-1].b,i);
}
else
val=val+v[i].t-v[i].b;
}
if(val>maxx)
maxx=val;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%hd%hd",&v[i].b,&v[i].t);
sort(v+1,v+n+1,cmp);
bfs(v[1].t-v[1].b,1);
printf("%ld\n",maxx);
    return 0;
}