Pagini recente » Cod sursa (job #1769654) | Cod sursa (job #508484) | Cod sursa (job #339285) | Cod sursa (job #3141726) | Cod sursa (job #1901117)
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int maxn = 100005;
int dp1[1005][1005]; /// dp[i][j] = numarul maxim de minute din primele i timp maxim j
int dp[maxn];
pair <int, int> v[maxn];
int p;
int cautbin(int x)
{
int st = 1;
int dr = p - 1;
int ret = 0;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(v[mij].second <= x)
{
st = mij + 1;
ret = mij;
}
else
dr = mij - 1;
}
return ret;
}
inline bool cmp(pair <int, int> a, pair <int, int> b)
{
if(a.second != b.second)
return a.second < b.second;
return a.first < b.first;
}
int main()
{
int n;
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1);
//if(n <= 1000)
//brut();
for(int i = 1; i <= n; i++)
{
p = i;
int durata = v[i].second - v[i].first;
dp[i] = dp[i - 1];
dp[i] = max(dp[i], dp[cautbin(v[i].first)] + durata);
}
out << dp[n];
return 0;
}