Pagini recente » Cod sursa (job #2350011) | Cod sursa (job #793388) | Cod sursa (job #316678) | Cod sursa (job #959383) | Cod sursa (job #1397012)
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
struct pii
{
int lo, hi;
pii(int _lo, int _hi)
{
lo = _lo;
hi = _hi;
}
bool operator< (const pii& rhs) const
{
if (hi != rhs.hi)
return (hi < rhs.hi);
return (lo < rhs.lo);
}
};
int n;
vector<int> dp, a, b;
vector<pii> p;
void read()
{
ifstream fin("heavymetal.in");
fin >> n;
for (int i = 1; i <= n; ++i)
{
int x, y;
fin >> x >> y;
p.push_back(pii(x, y));
}
fin.close();
}
void write()
{
ofstream fout("heavymetal.out");
fout << dp[n - 1] << '\n';
fout.close();
}
void findMaxTime()
{
sort(p.begin(), p.end());
for (size_t i = 0; i < p.size(); ++i)
{
a.push_back(p[i].lo);
b.push_back(p[i].hi);
dp.push_back(0);
}
dp[0] = b[0] - a[0];
for (int i = 1; i < n; ++i)
{
dp[i] = dp[i - 1];
vector<int>::iterator it = lower_bound(b.begin(), b.end(), a[i]);
if ((*it) > a[i])
{
if (it == b.begin())
continue;
else
--it;
}
int j = distance(b.begin(), it);
dp[i] = max(dp[i], dp[j] + b[i] - a[i]);
}
}
int main()
{
read();
findMaxTime();
write();
return 0;
}