Pagini recente » Cod sursa (job #2535362) | Cod sursa (job #1504022) | Cod sursa (job #1767827) | Cod sursa (job #1766269) | Cod sursa (job #2511585)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interv
{
int x, y;
};
int cmp(interv a, interv b)
{
if (a.y != b.y)
return a.y < b.y;
return a.x < b.x;
}
int cautBin(int st, int dr, int maxx, vector <interv> &v)
{
int answ = 0;
while(st <= dr)
{
int mij = (st + dr) / 2;
if (v[mij].y <= maxx)
{
answ = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return answ;
}
int main()
{
int n;
f >> n;
vector <interv> v(n + 1);
vector <int> dp(n + 2, 0);
for (int i = 0; i < n; i++)
f >> v[i].x >> v[i].y;
v[n].x = -1;
v[n].y = -1;
sort(v.begin(), v.begin() + n + 1, cmp);
// for (int i = 0; i <= n; i++)
// cout << v[i].x << " " << v[i].y << "\n";
//cout << "\n";
dp[0] = 0;
for (int i = 1; i <= n; i++)
{
int xi = v[i].x;
int yi = v[i].y;
int j = cautBin(0, n, xi, v);
// cout << xi << " " << yi << " " << j << "\n";
dp[i] = max(dp[i - 1], yi - xi + dp[j]);
}
g << dp[n];
return 0;
}