Cod sursa(job #2469200)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 6 octombrie 2019 16:36:59
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<bits/stdc++.h>
using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

const int NAX = 1e5 + 5;
vector<pair<int,int> >v;
int n, dp[ NAX ];

int cb(int i)
{
    int st = 0, dr = i, mij, sol = 0;
    while( st < dr )
    {
        mij = (st + dr + 1)/2;
        if( v[ mij ].second <= v[ i ].first )
        {
            st = mij;
        }
        else
            dr = mij - 1;
    }
    return st;
}

bool cmp(pair<int, int> a, pair<int, int>b)
{
    return a.second < b.second;
}


int main()
{
    f >> n;
    v.push_back({0,0});
    for(int x, y, i = 1 ; i <= n ; ++i)
    {
        f >> x >> y;
        v.push_back({x, y});
    }

    sort(v.begin() + 1, v.end(), cmp);

    dp[ 1 ] = abs( v[ 1 ].first - v[ 1 ].second );
    for(int i = 2 ; i <= n ; ++i)
    {
        int poz = cb(i);
        dp[ i ] = max( dp[ i - 1 ], dp[ poz ] + abs( v[ i ].first - v[ i ].second ));
    }
    g << dp[ n  ];
}