Pagini recente » Cod sursa (job #2792203) | Cod sursa (job #1338582) | Cod sursa (job #561778) | Cod sursa (job #1613694) | Cod sursa (job #595398)
Cod sursa(job #595398)
#include<stdio.h>
#include<algorithm>
#include<assert.h>
using namespace std;
#define MaxN 100100
#define mij (li + ls) / 2
#define ll long long
typedef struct
{
int x;
int y;
} xy;
xy A[MaxN];
ll B[MaxN];
int N;
ll MAX;
ll a;
ll b;
bool cmp(xy a,xy b)
{
return a.y < b.y;
}
ll max(ll a,ll b)
{
return a>b ? a:b;
}
ll binary_search(int li,int ls,int a)
{
if(li <= ls)
{
if(A[mij].y == a)
return B[mij];
else if(A[mij].y > a)
return binary_search(li , mij - 1 , a);
else
return binary_search(mij + 1 , ls , a);
}
else
return B[ls];
}
int main()
{
FILE *f = fopen("heavymetal.in","r");
FILE *g = fopen("heavymetal.out","w");
fscanf(f,"%d ",&N);
for(int i=1;i<=N;i++)
fscanf(f,"%llu %llu ",&A[i].x,&A[i].y);
sort(A+1,A+N+1,cmp);
B[1] = A[1].y - A[1].x;
for(int i=2;i<=N;i++)
{
B[i] = A[i].y - A[i].x + binary_search(1,i-1,A[i].x);
if(MAX < B[i])
MAX = B[i];
B[i] = MAX;
}
assert(MAX>=0);
fprintf(g,"%llu ",MAX);
fclose(g);
fclose(f);
return 0;
}