Cod sursa(job #347498)

Utilizator hendrikHendrik Lai hendrik Data 12 septembrie 2009 16:19:09
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <algorithm>
using namespace std;

void open(){
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
}

struct pii{
    int id,val,bgn;
    bool st;
    bool operator <(const pii &X)const{
        return (id<X.id) || (id==X.id && st<X.st);
    }
};

#define MAXN 100001
typedef long long ll;

int n,x1,x2;
ll f[MAXN],ans=0LL,maks=0LL;
pii X[MAXN*2];

int main(){
    open();
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        scanf("%d %d",&x1,&x2);
        X[2*i].id=x1;
        X[2*i].st=1;
        X[2*i].bgn=i;
        X[2*i].val=x2-x1;
        X[2*i+1].id=x2;
        X[2*i+1].st=0;
        X[2*i+1].val=x2-x1;
        X[2*i+1].bgn=i;
    }
    n*=2;
    sort(X,X+n);
    for (int i=0;i<n;i++){
        if (X[i].st){
            f[X[i].bgn]=f[X[i].bgn]+maks+(ll)X[i].val;
        }
        else {
            maks=max(maks,f[X[i].bgn]);
        }
        //cout<<X[i].st<<' '<<X[i].id<<' '<<X[i].bgn<<' '<<f[X[i].bgn]<<endl;
    }
    for (int i=0;i<n/2;i++) ans=max(ans,f[i]);
    printf("%lld\n",ans);
    //system("pause");
    return 0;
}