Cod sursa(job #1885790)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 20 februarie 2017 13:08:04
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <algorithm>

const int MAX_N = 1e5;
const int MAX_TIME = 1e9;

using namespace std;

int N;
int d[MAX_N + 1];

struct anakin{
    int start, end;
};

anakin concert[MAX_N + 1];

bool cmp(anakin a, anakin b) {
    return a.end >= b.end ? false : true;
}

int cautBin (int val) {
    int x = 0;
    int pas;
    pas = 1 << 16;

    while (pas) {
        if (x + pas <= N && concert[x + pas].end <= val) {
            x += pas;
        }

        pas >>= 1;
    }

    return x;
}

int main(){

    FILE *fin = fopen("heavymetal.in", "r");
    FILE *fout = fopen("heavymetal.out", "w");

    int i;
    int pos;
    int time_max = 0;

    fscanf(fin, "%d", &N);
    for (i = 1; i <= N; i++) {
        fscanf(fin, "%d %d", &concert[i].start, &concert[i].end);
    }

    sort(concert + 1, concert + N + 1, cmp);

    for (i = 1; i <= N; i++) {
        pos = cautBin(concert[i].start);
        d[i] = d[pos] + concert[i].end - concert[i].start;
        if (time_max < d[i])
            time_max = d[i];
    }

    fprintf(fout, "%d\n", time_max);

    fclose(fin);
    fclose(fout);
    return 0;
}