Cod sursa(job #1761457)

Utilizator mantisVraciu Stefan mantis Data 22 septembrie 2016 11:52:22
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <fstream>
#include<algorithm>
using namespace std;
struct trupa{ int x,y,l;} T[100001];
int n,P[100001];
long long V[100001];
struct cmp{
    bool operator() (int a, int b)
    {
        return T[a].y < T[b].y or (T[a].y == T[b].y and T[a].x < T[b].x);
    }
};
int caut_bin(int poz)
{
    int st = 1, dr = poz, m;
    while (st < dr)
    {
        m = (st + dr) / 2;
        if (T[P[m]].y > T[P[poz]].x) dr = m;
        else st = m + 1;
    }
    m = (st + dr) / 2;
    if (T[P[m]].y > T[P[poz]].x) -- m;
    return m;
}
int main()
{
    ifstream fin ("heavymetal.in");
    ofstream fout ("heavymetal.out");

    fin >> n;
    for(int i = 1; i <= n; i++)
    {
        fin>>T[i].x>>T[i].y;
        T[i].l = T[i].y - T[i].x;
        P[i]=i;
    }
    sort(1+P, 1+n+P, cmp());
    V[1]=T[P[1]].l;
    for(int i = 2; i <= n; i++)
    {
        int ant = caut_bin(i);
        V[i] = max (V[i-1], V[ant] + T[P[i]].l);
    }
    fout << V[n] << '\n';
    fout.close();
    return 0;
}