Pagini recente » Cod sursa (job #1591281) | Cod sursa (job #939697) | Cod sursa (job #163412) | Cod sursa (job #2467611) | Cod sursa (job #206226)
Cod sursa(job #206226)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
long n, o, nr1, nr2, i, max1, sumcur, f[100010];
struct mystruct {
long timp;
long stare;
long interval;
long dist;
};
vector < mystruct> v(200010);
bool cmp(mystruct c, mystruct d) {
if( c.timp < d.timp)
return true;
if( c.timp == d.timp && c.stare> d.stare)
return true;
return false;
}
int main() {
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%ld", &n);
o = 0;
for (i = 1; i <= n; ++i) {
scanf("%ld %ld", &nr1, &nr2);
++o;
v[o].timp = nr1;
v[o].stare = 0;
v[o].interval = i;
v[o].dist = nr2 - nr1;
++o;
v[o].timp = nr2;
v[o].stare = 1;
v[o].interval = i;
v[o].dist = nr2 - nr1;
}
sort( v.begin()+1, v.begin() + o + 1,cmp);
//qsort(v + 1, o, sizeof(v[0]), cmp);
/*for (i = 1; i <= o; ++i) {
printf("%ld %ld %ld\n", v[i].timp, v[i].stare, v[i].interval);
}*/
for (i = 1; i <= o; ++i) {
if (v[i].stare == 0) {
f[v[i].interval] = max1 + v[i].dist;
} else {
if (max1 < f[v[i].interval]) {
max1 = f[v[i].interval];
}
}
}
printf("%ld\n", max1);
return 0;
}