Cod sursa(job #2046888)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 24 octombrie 2017 10:51:39
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

FILE*f=fopen("heavymetal.in","r");
FILE*g=fopen("heavymetal.out","w");

long long t,i,j,n,u,x,y,optim[100005];

struct formatie {
    int t1,t2;
} a[100005];

int comp(formatie a,formatie b) {
    return a.t2<b.t2||(a.t2==b.t2&&a.t1>b.t1);
}

int main() {

    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++) {
        fscanf(f,"%d%d",&x,&y);
        a[i].t1=x; a[i].t2=y;
    }
    sort(a+1,a+n+1,comp);

    j=1;
    for(i=1;i<=a[n].t2;i++) {
        optim[i]=optim[i-1];
        while(a[j].t2==i) {
            optim[i]=max(optim[i],optim[a[j].t1]+a[j].t2-a[j].t1);
            j++;
        }
    }

    fprintf(g,"%d",optim[a[n].t2]);

    fclose(f); fclose(g);

    return 0;
}