Cod sursa(job #1224207)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 august 2014 02:17:18
Problema Orase Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#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=1;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;
}