Cod sursa(job #2304809)

Utilizator YetoAdrian Tonica Yeto Data 18 decembrie 2018 17:40:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>
#define X first
#define Y second
using namespace std;
int d[100001];
pair <int, int> A[100001];
int n, x, y, i, st ,dr, sol;

int main () {
    ifstream fin ("heavymetal.in");
    ofstream fout ("heavymetal.out");
    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>A[i].Y>>A[i].X;
    }

    sort(A+1, A+n+1);
    for (i=1;i<=n;i++) {
        d[i]=A[i].X-A[i].Y;
        if (d[i-1]>d[i])
            d[i]=d[i-1];
        st=1;
        dr=i-1;
        sol=0;
        while (st<=dr) {
            int mid = (st+dr)/2;
            if (A[i].Y>=A[mid].X) {
                sol=mid;
                st=mid+1;
            } else
                dr=mid-1;
        }
        if (d[sol]+A[i].X-A[i].Y>d[i])
            d[i]=d[sol]+A[i].X-A[i].Y;
    }

    fout<<d[n];
    return 0;
}