Pagini recente » Cod sursa (job #1288322) | Cod sursa (job #2426966) | Cod sursa (job #1475982) | Cod sursa (job #299189) | Cod sursa (job #2451712)
#include <bits/stdc++.h>
#define MAX 131072
using namespace std;
const int NMAX = 100020;
FILE *IN;
int N, poz;
int dp[NMAX];
vector <pair <int, int> > V;
int pos, sign;
char f[MAX];
inline void Read(int &nr){
sign = 0;
nr = 0;
while(f[pos] < '0' || f[pos] > '9'){
if(f[pos] == '-') sign=1;
pos++;
if(pos == MAX)
fread(f, MAX, 1, IN), pos = 0;
}
while(f[pos] >= '0' && f[pos] <= '9'){
nr = 10 * nr + f[pos++] - '0';
if(pos == MAX)
fread(f, MAX, 1, IN), pos = 0;
}
if(sign) nr =- nr;
}
int read(){
Read(N);
int a, b;
V.push_back(make_pair(0, 0));
for(int i = 1; i <= N; i++){
Read(a); Read(b);
V.push_back(make_pair(a, b));
}
}
bool cmp(pair <int, int> &a, pair <int, int> &b){
if(a.second < b.second)
return true;
if(a.first < b.first && a.second == b.second)
return true;
return false;
}
int binsearch(int x, int st, int nd){
int mid, last = 0;
while(st <= nd){
mid = (st + nd) / 2;
if(V[mid].second <= x){
last = mid;
st = mid + 1;
} else nd = mid - 1;
}
return last;
}
int main(){
IN = fopen("heavymetal.in", "r");
freopen("heavymetal.out", "w", stdout);
read();
sort(V.begin(), V.end(), cmp);
for(int i = 1; i <= N; i++){
if(V[i].first >= V[1].second)
pos = binsearch(V[i].first, 1, i);
else pos = 0;
dp[i] = max(dp[i - 1], dp[pos] + V[i].second - V[i].first);
}
printf("%d", dp[N]);
return 0;
}