Pagini recente » Cod sursa (job #2370072) | Cod sursa (job #366004) | Cod sursa (job #886003) | Cod sursa (job #5550) | Cod sursa (job #2784192)
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
struct seg
{
int lo, hi;
};
struct repr
{
int hi, maxlen;
};
struct cmpHeap
{
public : bool operator()(const repr &a, const repr &b)
{
return a.hi > b.hi;
};
};
bool cmpSort(seg a, seg b)
{
return a.lo < b.lo;
}
seg shows[NMAX];
priority_queue<repr, vector<repr>, cmpHeap> heap;
int main()
{
int maxCur, maxFin, n, i;
FILE *fin = fopen("heavymetal.in", "r");
fscanf(fin, "%d", &n);
for (i = 0; i < n; i++)
fscanf(fin, "%d%d", &shows[i].lo, &shows[i].hi);
sort(shows, shows + n, cmpSort);
fclose(fin);
maxCur = maxFin = 0;
for (i = 0; i < n; i++)
{
while (!heap.empty() && shows[i].lo >= heap.top().hi)
{
maxCur = max(maxCur, heap.top().maxlen);
heap.pop();
}
heap.push({shows[i].hi, maxCur + shows[i].hi - shows[i].lo});
maxFin = max(maxFin, maxCur + shows[i].hi - shows[i].lo);
}
FILE *fout = fopen("heavymetal.out", "w");
fprintf(fout, "%d", maxFin);
fclose(fout);
return 0;
}