Pagini recente » Cod sursa (job #2805585) | Cod sursa (job #2160812) | Cod sursa (job #1301605) | Cod sursa (job #2157003) | Cod sursa (job #1851054)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f, *g;
int rez, n;
struct interv
{
int x, y;
};
interv v[100001];
int dp[100001];
void readFile()
{
f = fopen("heavymetal.in", "r");
fscanf(f, "%d", &n);
int i;
for(i = 1; i <= n; i ++)
fscanf(f, "%d%d", &v[i].x, &v[i].y);
fclose(f);
}
bool cmp(interv a, interv b)
{
return (a.y < b.y);
}
int cautBin(int nr)
{
int i = 0, pas = 1 << 16;
while(pas != 0)
{
if((i + pas) <= n && v[i + pas].y <= nr)
i += pas;
pas /= 2;
}
return i;
}
void solve()
{
sort(v + 1, v + n + 1, cmp);
int i, poz;
for(i = 1; i <= n; i ++)
{
dp[i] = dp[i - 1];
poz = cautBin(v[i].x);
//printf("%d %d %d\n", poz, dp[poz] + v[poz].y - v[poz].x, dp[i]);
if(dp[poz] + v[i].y - v[i].x > dp[i])
dp[i] = dp[poz] + v[i].y - v[i].x;
}
rez = dp[n];
}
void printFile()
{
g = fopen("heavymetal.out", "w");
fprintf(g, "%d\n", rez);
fclose(g);
}
int main()
{
readFile();
solve();
printFile();
return 0;
}