Cod sursa(job #1972897)

Utilizator MoldovanMoldovan Moldovan Data 23 aprilie 2017 21:37:01
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[2000005];
struct dale
{
    int x,y;
};
dale p[200005];
bool sortcmp(dale k1,dale k2)
{
    if(k1.y<k2.y)return 1;
    if(k1.y>k2.y)return 0;
    if(k1.x<k2.x)return 1;
    return 0;
}
int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    int t , i;
    scanf("%d",&t);
    for(i=1;i<=t;i++)scanf("%d%d",&p[i].x,&p[i].y);
    sort(p+1,p+t+1,sortcmp);
    int k=1;
    for(i=1;i<=p[t].y;i++)
    {
        v[i]=v[i-1];
        while(i==p[k].y)
        {
            int val=v[p[k].x]+p[k].y-p[k].x;
            if(val>v[i])v[i]=val;
            k++;
        }
    }
    printf("%d",v[p[t].y]);
    return 0;
}