Pagini recente » Cod sursa (job #648121) | Cod sursa (job #2895075) | Cod sursa (job #2041020) | Cod sursa (job #1852226) | Cod sursa (job #2356605)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int N = 100001;
long long dp[N];
int a[N], b[N], d[100001];
int n;
struct numar{
int stt, drr;
};
numar v[100001];
int cmp(numar a, numar b){
if (a.drr == b.drr)
return a.stt < b.stt;
return a.drr < b.drr;
}
int caut(int k, int dr)
{
int st = 1, ans = 0, mij;
while (st <= dr)
{
mij = (st + dr) / 2;
if (v[mij].drr <= k)
{
ans = mij;
st = mij + 1;
}
else dr = mij - 1;
}
return ans;
}
int main()
{
int n, ans;
f >> n;
for (int i = 1; i <= n; i++)
{
f >> v[i].stt >> v[i].drr;
}
sort (v + 1, v + n + 1, cmp);
dp[1] = v[1].drr - v[1].stt;
for (int i = 2; i <= n; i++)
{
ans = caut(v[i].stt, i - 1);
dp[i] = max(dp[i - 1], dp[ans] + v[i].drr - v[i].stt);
}
g << dp[n];
return 0;
}