Cod sursa(job #288771)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 26 martie 2009 09:05:48
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<algorithm>
using namespace std;

#define DIM 100001

int n,sol[DIM];

struct timp{
    int x,y;};
timp a[DIM];

void solve(){
    int i,j,max0;
    
    scanf("%d",&n);
    for(i=1,max0=0; i<=n; ++i){
        scanf("%d%d",&a[i].x,&a[i].y);
        if(a[i].y>max0)
            max0=a[i].y;}
    for(i=1; i<=max0; ++i){
        sol[i]=sol[i-1];
        for(j=1; j<=n; ++j)
            if(a[j].y==i)
                sol[i]=max(sol[i],sol[a[j].x]+a[j].y-a[j].x);}
    printf("%d",sol[max0]);}
    
int main(){
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    solve();
    return 0;}