Pagini recente » Cod sursa (job #628783) | Cod sursa (job #1610535) | Cod sursa (job #589558) | Cod sursa (job #2189270) | Cod sursa (job #1206411)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MaxBAND 2000
struct Band
{
int left;
int right;
int l;
} band;
vector<Band> bands;
int best[3800000];
bool sort_right(Band a, Band b)
{
return a.right < b.right;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int n, i, val, cpy, j, k, maxx=0;
scanf("%d", &n);
for(i=0; i<n; i++)
{
scanf("%d %d", &band.left, &band.right);
maxx = max(maxx,band.right);
band.l = band.right - band.left;
bands.push_back(band);
}
sort(bands.begin(), bands.end(), sort_right);
best[bands[0].right] = bands[0].l;
for(i=1; i<=maxx; i++)
{
best[i] = best[i-1];
for(j=0; j<bands.size() && bands[j].right < i; j++);
for(; bands[j].right == i; j++)
{
best[i] = max(best[i], best[bands[j].left] + bands[j].right - bands[j].left);
}
}
printf("%d", best[maxx]);
return 0;
}