Cod sursa(job #2575836)

Utilizator Codrut112Codrut Copas Codrut112 Data 6 martie 2020 15:40:42
Problema Heavy metal Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int n,i,dp[100000],mx,j,l;
struct metal
{
    int start;
    int sf;
} v[100000];
bool comp(metal a,metal b)
{
    if(a.sf==b.sf)return a.start<b.start;
    return a.sf<b.sf;
}

int caut(int poz,int val)
{
    int mid=0;
    int st=1;
    int dr=poz-1;
    poz=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(v[mid].sf<=val )
        {
            poz=mid;
            st=mid+1;
        }
        else                  dr=mid-1;

    }
    return poz;

}

int main()
{
    f>>n;
    for(i=1; i<=n; i++)f>>v[i].start>>v[i].sf;
      sort(v+1,v+n+1,comp);
    dp[1]=v[1].sf-v[1].start;

    for(i=2; i<=n; i++)
    {
        j=caut(i,v[i].start);

        dp[i]=max(dp[i-1],dp[j]+v[i].sf-v[i].start) ;

    }
    g<<dp[n];

}