Pagini recente » Cod sursa (job #1755994) | Cod sursa (job #204239) | Cod sursa (job #1878099) | Cod sursa (job #1148870) | Cod sursa (job #2536141)
#include <fstream>
#include <algorithm>
#define a first
#define b second
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
pair <int,int> v[100001];
int best[100001];
int n;
int cautbin(int val) {
int r=0,pas=1<<16;
while(pas) {
if(r+pas<=n&&v[r+pas].b<=val)
r+=pas;
pas/=2;
}
return r;
}
int main() {
int i,x;
in>>n;
for(i=1; i<=n; i++)
in>>v[i].b>>v[i].a;
sort(v+1,v+n+1);
for(i=1; i<=n; i++)
v[i].a^=v[i].b^=v[i].a^=v[i].b;
for(i=1; i<=n; i++) {
x=cautbin(v[i].a);
best[i]=max(best[i-1],best[x]+v[i].b-v[i].a);
}
out<<best[n];
return 0;
}