Cod sursa(job #2540295)

Utilizator Iulia14iulia slanina Iulia14 Data 6 februarie 2020 22:45:15
Problema Heavy metal Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");
/*struct ura{
    int x,y;
};
ura v[100005];*/
struct ura{
    int x,y,tip,ind;
};
ura v[100005];
bool cmp (ura a,ura b)
{
    int aa,bb;
    if (a.tip==1)
        aa=a.x;
    else
        aa=a.y;
    if (b.tip==1)
        bb=b.x;
    else
        bb=b.y;
    if (aa<bb)
        return true;
    else
    if (aa>bb)
        return false;
    else
    if (a.tip<b.tip)
        return false;
    return true;
}
int dp[100005][2];
int main()
{
    int n,sf,nr,i;
    cin>>n;
    for (i=1;i<=n;i++)
    {
        cin>>v[i*2-1].x>>v[i*2-1].y;
        v[i*2-1].tip=1;
        v[i*2].tip=2;
        v[i*2-1].ind=v[i*2].ind=i;
        v[i*2].x=v[i*2-1].x;
        v[i*2].y=v[i*2-1].y;
    }
    sort (v+1,v+2*n+1,cmp);
    int maxi=0;
    for (i=1;i<=2*n;i++)
    {
        if (v[i].tip==1)
            dp[v[i].ind][0]=maxi;
        else
        {
            dp[v[i].ind][1]=max(maxi,v[i].y-v[i].x+dp[v[i].ind][0]);
        }
        maxi=max(maxi,dp[v[i].ind][1]);
    }
    cout<<maxi;
    return 0;
}