Cod sursa(job #2027402)

Utilizator workwork work work Data 26 septembrie 2017 01:41:47
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <bits/stdc++.h>

#define a first
#define b second

using namespace std;

ifstream F("heavymetal.in");
ofstream G("heavymetal.out");

int n, st, dr, mij, Tm, x, y;
long long dp[1<<17];
//pair<int, int> p[100003], v[100003];
vector<int> w[1<<17];

int main()
{
    /**
    F >> n;
    for(int i = 1; i <= n; ++ i) F >> p[i].a >> p[i].b, v[i]=p[i];
    sort(v+1, v+n+1);
    for(int i = 1; i <= n; ++ i)
    {
        st=1;dr=n;
        while(st<=dr)
        {
            mij=(st+dr)>>1;
            if(v[mij].a==p[i].a) {p[i].a=mij;break;}
            else if(v[mij].a<p[i].a) st=mij+1;
            else dr=mij-1;
        }
        st=1;dr=n;
        while(st<=dr)
        {
            mij=(st+dr)>>1;
            if(v[mij].b==p[i].b) {p[i].b=mij; w[mij].push_back(i);break;}
            else if(v[mij].b<p[i].b) st=mij+1;
            else dr=mij-1;
        }
    }
    vector<int>::iterator it;
    for(int i = 1; i <= n; ++ i)
        if(w[i].size())
        {
            dp[i]=dp[i-1];dp1[i]=dp1[i-1];
            for(it=w[i].begin(); it!=w[i].end();++it)
                if(dp[*it]+1>dp[i]) dp[i]=dp[*it]+1, dp1[i]=dp1[*it]+v[i].b-v[i].a;
                else if(dp[*it]+1==dp[i]&&dp1[*it]+v[i].b-v[i].a>dp1[i]) dp1[i]=dp1[*it]+v[i].b-v[i].a;
        }
    G << dp1[n];*/
    F >> n;
    for(int i = 1; i <= n; ++ i) {F >> x >> y, w[y].push_back(x); Tm=max(Tm, y);}
    vector<int>::iterator it;
    for(int i = 1; i <= Tm; ++ i)
    {
        dp[i]=dp[i-1];
        for(it=w[i].begin(); it!=w[i].end();++it)
            if(dp[i]<dp[*it]+i-(*it)) dp[i]=dp[*it]+i-(*it);
    }
    G<<dp[Tm];
    return 0;
}