Pagini recente » Cod sursa (job #2098683) | Cod sursa (job #2132947) | Cod sursa (job #896124) | Cod sursa (job #2740326) | Cod sursa (job #1885790)
#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;
}