Pagini recente » Cod sursa (job #3261408) | Cod sursa (job #2301586) | Cod sursa (job #297596) | Cod sursa (job #2093861) | Cod sursa (job #2505571)
#include <bits/stdc++.h>
#define NMax 100005
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct Concert
{
int st, dr, timp;
};
int n, dp[NMax];
Concert Interval[NMax];
inline bool Sortare(Concert x, Concert y)
{
return (x.dr < y.dr);
}
void Citire()
{
int i;
fin >> n;
for(i = 1; i <= n; i++)
{
fin >> Interval[i].st >> Interval[i].dr;
Interval[i].timp = Interval[i].dr - Interval[i].st;
}
sort(Interval + 1, Interval + n + 1, Sortare);
}
int CautareBinara(int x, int capat)
{
int st = 1, dr = capat, sol = 0, mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if(Interval[mij].dr <= x)
{
sol = mij;
st = mij + 1;
}
else dr = mij - 1;
}
return sol;
}
void Rezolvare()
{
for(int i = 1; i <= n; i++)
dp[i] = max(dp[CautareBinara(Interval[i].st, i - 1)] + Interval[i].timp, dp[i - 1]);
fout << dp[n];
fin.close();
fout.close();
}
int main()
{
Citire();
Rezolvare();
return 0;
}