Pagini recente » Cod sursa (job #998945) | Cod sursa (job #1273605) | Cod sursa (job #2364869) | Cod sursa (job #1848808) | Cod sursa (job #1288370)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int NMAX = 100000;
struct concert{
int a,b;
};
concert v[NMAX + 1];
int sol[NMAX + 1],n;
void read()
{
in>>n;
for(int i = 1 ; i <= n ; i++)
in>>v[i].a>>v[i].b;
in.close();
}
bool cmp(concert x,concert y){
return x.b < y.b;
}
int bin_search(int left,int right,int val)
{
int mid,s = -1;
while(left <= right){
mid = (left+right)>>1;
if(v[mid].b <= val)
left = mid + 1,s = mid;
else
right = mid - 1;
}
return s;
}
void solve()
{
sort(v+1,v+n+1,cmp);
sol[1] = v[1].b-v[1].a;
for(int i = 2 ; i <= n ; i++){
sol[i] = sol[i-1];
int key = bin_search(1,i-1,v[i].a);
if(key != -1)
sol[i] = max(sol[i],sol[key] + (v[i].b-v[i].a));
else
sol[i] = max(sol[i],v[i].b-v[i].a);
}
out<<sol[n];
out.close();
}
int main()
{
read();
solve();
return 0;
}