Pagini recente » Cod sursa (job #2834753) | Cod sursa (job #2690409) | Cod sursa (job #2125076) | Cod sursa (job #2869615) | Cod sursa (job #2050124)
#include <bits/stdc++.h>
class band_t final
{
public:
int start, end;
bool operator<(const band_t &band) const
{
return end < band.end;
}
};
band_t bnd[100005];
long long dyn[100005];
int n;
int binary_search(int val)
{
int step = ox3f3f3f3f, pos = 0;
while (step != 0)
{
if (pos + step <= n && bnd[pos + step].end <= val)
pos += step;
step /= 2;
}
return pos;
}
int main()
{
std::ifstream in("heavymetal.in");
in >> n;
for (auto i = 1; i <= n; ++i)
in >> bnd[i].start >> bnd[i].end;
std::sort(bnd + 1, bnd + n + 1);
dyn[1] = bnd[1].end - bnd[1].start;
for (auto i = 2; i <= n; ++i)
dyn[i] = std::max((bnd[i].end - bnd[i].start) + dyn[binary_search(bnd[i].start)], dyn[i - 1]);
std::ofstream("heavymetal.out") << dyn[n];
}