Cod sursa(job #1981986)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 17 mai 2017 14:57:02
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<fstream>
#include<algorithm>
using namespace std;
struct spec{
    int x1,y1;
}A[100001];
int N,S,i,j,o,y[100001];
bool cmp(spec x,spec y){
    if(x.y1>y.y1)return false;
    if(x.y1==y.y1 && x.x1>y.x1)return false;
    return true;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;++i)
        scanf("%d%d",&A[i].x1,&A[i].y1);
    sort(A+1,A+N+1,cmp);
    o=1;
    for(i=1;i<=A[N].y1;++i){
        y[i]=y[i-1];
        while(i==A[o].y1){
            int val=A[o].y1-A[o].x1+y[A[o].x1];
            y[i]=max(y[i],val);
            ++o;
        }
    }
    printf("%d",y[A[N].y1]);
    return 0;
}