Pagini recente » Cod sursa (job #3310405) | Cod sursa (job #2873097) | Borderou de evaluare (job #3332240) | Cod sursa (job #336287) | Cod sursa (job #3326398)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int dp[100005], n;
struct concert
{
int start, finall;
}c[100005];
bool cmp(concert A, concert B)
{
if(A.finall < B.finall)
return 1;
else if(A.finall > B.finall)
return 0;
else
{
if(A.start < B.start)
return 1;
else
return 0;
}
}
int cb(int st, int dr, int x)
{
int mij, poz = -1;
while(st <= dr)
{
mij = (st + dr) / 2;
if(c[mij].finall <= x)
{
poz = mij;
st = mij + 1;
}
else if(c[mij].finall > x)
dr = mij - 1;
}
return poz;
}
int main()
{
int i, j;
fin >> n;
for(i = 1; i <= n; i++)
fin >> c[i].start >> c[i].finall;
sort(c + 1, c + n + 1, cmp);
for(i = 1; i <= n; i++)
{
j = cb(1, i - 1, c[i].start);
dp[i] = max(dp[i-1], c[i].finall - c[i].start + dp[j]);
}
fout << dp[n];
return 0;
}