Cod sursa(job #2383201)

Utilizator Iorgus08Iorgus Serghei Cicala Iorgus08 Data 19 martie 2019 10:27:36
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

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

const int maxN=1e5+5;

pair <int, int> v[maxN];
int p, i, j, N, stanga, dreapta, d[maxN];

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

int main()
{
    in >> N;
    for(i=1; i<=N; i++)
    {
        in >> v[i].first;
    }
    for(i=1; i<=N; i++)
    {
        in >> v[i].second;
    }
    sort (v + 1, v + N + 1, compare);
    d[1] = v[1].second - v[1].first;
    for (i=2; i<=N; i++)
    {
        stanga = 1;
        dreapta = i - 1;
        p = 0;
        while (stanga <= dreapta)
        {
            int mijloc = (stanga + dreapta)/2;
            if (v[i].first >= v[mijloc].second)
            {
                stanga = mijloc + 1;
            }
            else
            {
                dreapta = mijloc - 1;
            }
        }
        d[i] = max (d[i-1], d[p] + (v[i].second - v[i].first));
    }
    out << d[N];
    return 0;
}