Pagini recente » Cod sursa (job #1627733) | Cod sursa (job #3129169) | Cod sursa (job #2737730) | Cod sursa (job #1831392) | Cod sursa (job #2304809)
#include <fstream>
#include <algorithm>
#define X first
#define Y second
using namespace std;
int d[100001];
pair <int, int> A[100001];
int n, x, y, i, st ,dr, sol;
int main () {
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>A[i].Y>>A[i].X;
}
sort(A+1, A+n+1);
for (i=1;i<=n;i++) {
d[i]=A[i].X-A[i].Y;
if (d[i-1]>d[i])
d[i]=d[i-1];
st=1;
dr=i-1;
sol=0;
while (st<=dr) {
int mid = (st+dr)/2;
if (A[i].Y>=A[mid].X) {
sol=mid;
st=mid+1;
} else
dr=mid-1;
}
if (d[sol]+A[i].X-A[i].Y>d[i])
d[i]=d[sol]+A[i].X-A[i].Y;
}
fout<<d[n];
return 0;
}