Pagini recente » Cod sursa (job #967654) | Cod sursa (job #1151599) | Cod sursa (job #723900) | Cod sursa (job #150071) | Cod sursa (job #1224206)
#include <fstream>
using namespace std;
ifstream f("orase.in");
ofstream g("orase.out");
long n,i,maxi,maxim,m;
struct point{long x,y;}a[1000002];
void interc(long st,long m,long dr)
{
point b[dr-st+2];
long i=st,j=m+1,k=0;
while(i<=m && j<=dr)
if(a[i].x<a[j].x||(a[i].x==a[j].x && a[i].y<a[j].y)) b[++k]=a[i++];
else b[++k]=a[j++];
for(;i<=m;i++) b[++k]=a[i];
for(;j<=dr;j++) b[++k]=a[j];
for(i=1;i<=k;i++) a[i+st-1]=b[i];
}
void mergesort(long st,long dr)
{
if(st>=dr) return;
long m=(st+dr)>>1;
mergesort(st,m);
mergesort(m+1,dr);
interc(st,m,dr);
}
int main()
{
f>>m>>n;
for(i=1;i<=n;i++)
f>>a[i].x>>a[i].y;
f.close();
mergesort(1,n);
for(i=2;i<=n;i++)
{
maxi+=a[i].x-a[i-1].x;
maxi=max(maxi,a[i].x-a[i-1].x+a[i-1].y);
if(maxi+a[i].y>maxi) maxim=maxi+a[i].y;
}
g<<maxim;
g.close();
return 0;
}