Pagini recente » Cod sursa (job #32617) | Cod sursa (job #258406) | Cod sursa (job #769316) | Cod sursa (job #279955) | Cod sursa (job #852650)
Cod sursa(job #852650)
#include <fstream>
#include <algorithm>
#define MAX 100005
using namespace std;
struct spectacol
{
int s, e;
} v[MAX];
int n;
long long dp[MAX];
bool cmp(spectacol a, spectacol b) {return a.e < b.e;}
long long src(int val, int r)
{
int l = 1, m;
long long ans = 0;
while(l <= r)
{
m = (l + r) >> 1;
if(v[m].e <= val)
{
ans = max(ans, dp[m]);
l = m + 1;
}
else
r = m - 1;
}
return ans;
}
int main()
{
ifstream in("heavymetal.in");
in>>n;
for(int i = 1; i <= n; i++) in>>v[i].s>>v[i].e;
in.close(); sort(v + 1, v + n + 1, cmp);
for(int i = 1; i <= n; i++)
dp[i] = max(dp[i - 1], src(v[i].s, i - 1) + v[i].e - v[i].s);
ofstream out("heavymetal.out"); out<<dp[n]; out.close();
return 0;
}