Pagini recente » Cod sursa (job #590761) | Cod sursa (job #1654371) | Cod sursa (job #550353) | Cod sursa (job #3236725) | Cod sursa (job #234610)
Cod sursa(job #234610)
#include <stdio.h>
#include <algorithm>
using namespace std;
int A[100010],B[100010];
int timp[100010],rez[100010];
int sir[100010],n;
long maxim;
struct cmp
{
bool operator()(const int a, const int b) const
{
return (B[a]<B[b]);
}
};
void calcul()
{
timp[1]=B[sir[0]];
rez[1]=B[sir[0]]-A[sir[0]];
maxim=rez[1];
for (int i=1;i<n;i++)
{
timp[i+1]=timp[i];
rez[i+1]=rez[i];
int j=i;
while (j && timp[j]>A[sir[i]])
j--;
if (rez[i+1]<rez[j]+(B[sir[i]]-A[sir[i]]))
{
rez[i+1]=rez[j]+(B[sir[i]]-A[sir[i]]);
timp[i+1]=B[sir[i]];
maxim=rez[i+1];
}
}
printf("%ld\n",maxim);
}
int main ()
{
freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
scanf ("%d",&n);
for (int i=0;i<n;i++)
{
sir[i]=i;
scanf ("%d %d",&A[i],&B[i]);
}
sort(sir,sir+n,cmp());
calcul();
return 0;
}