Pagini recente » Cod sursa (job #1498292) | Cod sursa (job #2987996)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
long long dp[100005];
pair<int, int> t[100005];
bool cmp(pair<int, int> A, pair<int, int> B)
{
return A.second < B.second;
}
int CB(int x)
{
int st, dr, mij, p;
st = 1; dr = n; p = 0;
while (st <= dr)
{
mij = (st + dr) / 2;
if (t[mij].second <= x)
{
st = mij + 1;
p = mij;
}
else dr = mij - 1;
}
return p;
}
int main()
{
int p;
fin >> n;
for (int i = 1; i <= n; i++)
fin >> t[i].first >> t[i].second;
sort(t + 1, t + n + 1, cmp);
dp[1] = t[1].second - t[1].first;
for (int i = 1; i <= n; i++)
{
p = CB(t[i].first);
dp[i] = dp[p] + t[i].second - t[i].first;
}
fout << dp[n] << "\n";
return 0;
}