Pagini recente » Cod sursa (job #239258) | Cod sursa (job #553046) | Cod sursa (job #668485) | Cod sursa (job #2409489) | Cod sursa (job #1851807)
#include <stdio.h>
#include <algorithm>
struct conc
{ int a; int b;int nr;};
conc v[100001];
using namespace std;
bool cmp ( conc x, conc y) {
if ( x.b < y.b )
return 1;
return 0;
}
int main()
{
FILE *fin, *fout;
int n, i, st, dr, o, m;
fin = fopen ( "heavymetal.in", "r" );
fout = fopen ( "heavymetal.out", "w" );
fscanf ( fin, "%d", &n );
for ( i = 1; i <= n; i++)
fscanf ( fin, "%d%d", &v[i].a, &v[i].b);
sort ( v + 1, v + n + 1, cmp);
for ( i = 1; i <= n; i++) {
st = 1;
dr = i - 1;
o = 0;
while ( st <= dr )
{
m = (st + dr);
if ( v[m].a <= v[i].b )
{
o = m;
st = m + 1;
}
else
dr = m - 1;
}
if(v[i - 1].nr > v[i].a + v[i].b - v[o].nr)
v[i].nr = v[i - 1].nr;
else
v[i].nr = v[i].a + v[i].b - v[o].nr;
}
fprintf ( fout, "%d", v[n].nr);
fclose ( fin );
fclose ( fout );
return 0;
}