Pagini recente » Cod sursa (job #2773730) | Cod sursa (job #216961) | Cod sursa (job #1765662) | Cod sursa (job #380772) | Cod sursa (job #2498018)
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMax = 100000;
int dp[NMax + 5];
int n;
struct Formatie
{
int start, end;
} form[NMax + 5];
bool operator < (Formatie a, Formatie b)
{
if(a.end != b.end)
return a.end < b.end;
else
return a.start < b.start;
}
void read()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> form[i].start >> form[i].end;
sort(form + 1, form + n + 1);
}
int cautBin(int st, int dr, int inceput)
{
int mij, sol = 0;
while (st <= dr)
{
mij = (st + dr) / 2;
if(form[mij].end <= inceput)
{
st = mij + 1;
sol = mij;
}
else
dr = mij - 1;
}
return sol;
}
int main()
{
read();
for (int i = 1; i <= n; i++)
{
int durata = form[i].end - form[i].start;
dp[i] = max(dp[i - 1], dp[cautBin(0, i, form[i].start)] + durata);
}
fout << dp[n];
}