Cod sursa(job #2469174)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 6 octombrie 2019 16:23:31
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 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 - 1, mij, sol = 0;
    while( st <= dr )
    {
        mij = st + ( dr - st )/2;
        if( v[ mij ].second <= v[ i ].first )
        {
            sol = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return sol;
}

bool cmp(pair<int, int> a, pair<int, int> b)
{

}

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

    sort(v.begin(), v.end());

    dp[ 0 ] = abs( v[ 0 ].first - v[ 0 ].second );
    for(int i = 1 ; 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 - 1 ];
}