Pagini recente » Cod sursa (job #1574191) | Cod sursa (job #2944079) | Cod sursa (job #1200512) | Cod sursa (job #1359545) | Cod sursa (job #2287488)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 100000;
int DP[NMAX + 5], N;
struct interval{int start, finish;} V[NMAX + 5];
inline bool compare(interval a, interval b) {
return a.finish < b.finish;
}
int caut(int st, int dr, int val)
{
int ans = 0;
while(st <= dr) {
int mid = (st + dr) >> 1;
if(V[mid].finish <= val) {
ans = DP[mid];
st = mid + 1;
} else {
dr = mid - 1;
}
}
return ans;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
fin >> V[i].start >> V[i].finish;
sort(V + 1, V + N + 1, compare);
for(int i = 1; i <= N; i++)
DP[i] = max(DP[i - 1], caut(1, i - 1, V[i].start) + V[i].finish - V[i].start);
fout << DP[N] << '\n';
return 0;
}