Cod sursa(job #2094055)

Utilizator dianamariaDiana Cataros dianamaria Data 24 decembrie 2017 22:40:35
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
const int N=100001;
struct poz
{
    int x,y;
};
poz v[N];
int a[N];
bool cmp(poz a,poz b)
{
    if (a.y>b.y)
        return false;
    if (a.x>b.x && a.y==b.y)
        return false;
    return true;
}

int main()
{
    int n,i,s=0,pozcurr=1;
    in>>n;
    for (i=1;i<=n;i++)
        in>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for (i=1;i<=v[n].y;i++)
    {
        a[i]=a[i-1];
        while (i==v[pozcurr].y)
        {
            a[i]=max(a[i],v[pozcurr].y-v[pozcurr].x+a[v[pozcurr].x]);
            pozcurr++;
        }
    }
    out<<a[v[n].y];
    return 0;
}