Pagini recente » Cod sursa (job #446813) | Cod sursa (job #116215) | Cod sursa (job #1363333) | Cod sursa (job #2657628) | Cod sursa (job #1206848)
#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;
}