Cod sursa(job #1851054)

Utilizator Coroian_DavidCoroian David Coroian_David Data 19 ianuarie 2017 10:57:51
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>

#include <algorithm>

using namespace std;

FILE *f, *g;

int rez, n;

struct interv
{
    int x, y;
};

interv v[100001];

int dp[100001];

void readFile()
{
    f = fopen("heavymetal.in", "r");

    fscanf(f, "%d", &n);

    int i;
    for(i = 1; i <= n; i ++)
        fscanf(f, "%d%d", &v[i].x, &v[i].y);

    fclose(f);
}

bool cmp(interv a, interv b)
{
    return (a.y < b.y);
}

int cautBin(int nr)
{
    int i = 0, pas = 1 << 16;

    while(pas != 0)
    {
        if((i + pas) <= n && v[i + pas].y <= nr)
            i += pas;

        pas /= 2;
    }

    return i;
}

void solve()
{
    sort(v + 1, v + n + 1, cmp);

    int i, poz;
    for(i = 1; i <= n; i ++)
    {
        dp[i] = dp[i - 1];

        poz = cautBin(v[i].x);

        //printf("%d %d %d\n", poz, dp[poz] + v[poz].y - v[poz].x, dp[i]);

        if(dp[poz] + v[i].y - v[i].x > dp[i])
            dp[i] = dp[poz] + v[i].y - v[i].x;
    }

    rez = dp[n];
}

void printFile()
{
    g = fopen("heavymetal.out", "w");

    fprintf(g, "%d\n", rez);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}