Pagini recente » Cod sursa (job #1725731) | Cod sursa (job #2622589) | Cod sursa (job #1385554) | Cod sursa (job #275207) | Cod sursa (job #2336630)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
bool cmp(const pii &a, const pii &b)
{
if(a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
int main()
{
ifstream in("heavymetal.in");
int n;
in >> n;
vector<pii> v(n);
for(auto &p:v)
in >> p.first >> p.second;
in.close();
sort(v.begin(), v.end(), cmp);
vector<int> dp(n);
for(int i = 0; i < n; ++i)
{
int st = 0, dr = n, mid;
int p = -1;
while(st <= dr)
{
mid = (st + dr) / 2;
if(v[mid].second <= v[i].first)
{
p = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
if(i > 0)
dp[i] = dp[i-1];
dp[i] = max(dp[i], (p == -1 ? 0 : dp[p]) + v[i].second - v[i].first);
}
ofstream out("heavymetal.out");
out << dp.back();
out.close();
return 0;
}