Pagini recente » Cod sursa (job #3211681) | Cod sursa (job #1089475) | Cod sursa (job #2346304) | Cod sursa (job #2750796) | Cod sursa (job #731316)
Cod sursa(job #731316)
#include <fstream>
#include <algorithm>
#define nmax 100005
using namespace std;
int n, d[nmax];
pair<int,int> v[nmax];
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
bool cmp(pair<int,int> a, pair<int,int> b){
return a.second < b.second;
}
void citeste(){
f >> n;
for(int i=1; i<=n; i++){
int x,y;
f >> x >> y;
v[i]=(make_pair(x, y));
}
sort(v+1, v+n+1, cmp);
}
int cb(int val){
int st=1;
int dr=n;
int rez = 0;
while(st <= dr){
int mij = (st + dr) / 2;
if (v[mij].second <= val){
rez = mij;
st = mij+1;
}else dr = mij-1;
}
return rez;
}
void rezolva(){
d[0] = 0;
for(int i=1; i<=n; i++){
int start = v[i].first;
int final = v[i].second;
int poz = cb(start);
d[i] = max(d[i-1], d[poz] + (final - start));
}
g << d[n] << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}