Pagini recente » Cod sursa (job #2743265) | Cod sursa (job #1998263) | Cod sursa (job #323976) | Cod sursa (job #2912674) | Cod sursa (job #2685800)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 100000;
struct interval{
long long start, finish, val;
bool operator < (const interval &a) const{
if(finish == a.finish)
return start < a.start;
else return finish < a.finish;
}
};
vector<interval> v;
long long dp[NMAX+5];
int cautare_binara(int st, int dr, interval x)
{
int sol = -1;
while(st <= dr)
{
int mid = (st + dr) >>1;
if(v[mid].finish <= x.start)
{
sol = mid;
st = mid + 1;
}
else dr = mid -1;
}
return sol + 1;
}
int main()
{
int n, i;
long long a, b;
fin>>n;
for(i = 1; i <=n ;i++)
{
fin>>a>>b;
interval aux;
aux.start = a;
aux.finish = b;
aux.val = b - a;
v.push_back(aux);
}
sort(v.begin(), v.end());
for(int i =0; i < v.size(); i++)
{
int index = cautare_binara(0, i -1, v[i]);
dp[i + 1] = max(dp[i], dp[index] + v[i].val);
}
fout<<dp[n]<<"\n";
return 0;
}