Cod sursa(job #1206848)

Utilizator AndreeaBaltaBalta Andreea Cristina AndreeaBalta Data 11 iulie 2014 13:01:24
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct formatii{
    int x, y;
};
formatii c[100001];

int d[100001];

bool cmp(formatii a, formatii b)
{
    return a.y < b.y;
}
int binary_search(int st, int dr, int val)
{
    int med, last = -1;
    while(st <= dr)
    {
        med = st + (dr - st) / 2;
        if(c[med].y <= val)
            last = med,st = med + 1;
        else
            dr = med - 1;
    }
    return last;
}
int main()
{
    FILE *in,*out;
    in = fopen("heavymetal.in", "r");
    out = fopen("heavymetal.out", "w");
    int n, i, aux;
    fscanf(in, "%d", &n);
    for(i = 1; i<= n; i++)
        fscanf(in, "%d%d", &c[i].x, &c[i].y);
    sort(c + 1, c + n + 1, cmp);
    for(i = 1; i<= n; i++)
    {
        d[i] = d[i-1];
        aux = binary_search(1, i - 1, c[i].x);
        if(aux == -1)
        {
            if(d[i] < c[i].y - c[i].x)
                d[i] = c[i].y - c[i].x;
        }
        else
        {
            if(d[i] < d[aux] + c[i].y - c[i].x)
                d[i] = d[aux] + c[i].y - c[i].x;
        }
    }
    fprintf(out, "%d", d[n]);
    return 0;
}