Pagini recente » Cod sursa (job #704393) | Cod sursa (job #2772915) | Cod sursa (job #682985) | Cod sursa (job #2409745) | Cod sursa (job #2383201)
#include <bits/stdc++.h>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int maxN=1e5+5;
pair <int, int> v[maxN];
int p, i, j, N, stanga, dreapta, d[maxN];
bool compare(pair <int, int> a, pair <int, int> b)
{
return a.second < b.second;
}
int main()
{
in >> N;
for(i=1; i<=N; i++)
{
in >> v[i].first;
}
for(i=1; i<=N; i++)
{
in >> v[i].second;
}
sort (v + 1, v + N + 1, compare);
d[1] = v[1].second - v[1].first;
for (i=2; i<=N; i++)
{
stanga = 1;
dreapta = i - 1;
p = 0;
while (stanga <= dreapta)
{
int mijloc = (stanga + dreapta)/2;
if (v[i].first >= v[mijloc].second)
{
stanga = mijloc + 1;
}
else
{
dreapta = mijloc - 1;
}
}
d[i] = max (d[i-1], d[p] + (v[i].second - v[i].first));
}
out << d[N];
return 0;
}