Pagini recente » Cod sursa (job #2289753) | Cod sursa (job #1105218) | Cod sursa (job #2713891) | Cod sursa (job #2824868) | Cod sursa (job #3281563)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, i, j, dp[100001];
vector <pair<int, int>> v;
int cb(int st, int dr, int x)
{
int poz = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(v[mij].second <= x)
{
poz = mij;
st = mij + 1;
}
else if(v[mij].second > x)
dr = mij - 1;
}
return poz;
}
bool cmp (pair<int, int> a, pair<int, int> b)
{
return a.second < b.second;
}
int main()
{
fin >> n;
for(i = 0; i < n; i++)
{
int x, y;
fin >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end(), cmp);
dp[0] = v[0].second - v[0].first;
for(i = 1; i < n; i++){
j = cb(0, i - 1, v[i].first);
if(j != -1)
dp[i] = max(dp[i - 1], (v[i].second - v[i].first) + dp[j]);
else
dp[i] = dp[i - 1];
}
fout << dp[n - 1];
return 0;
}