Cod sursa(job #545458)

Utilizator dragomirdragomir alex dragomir Data 3 martie 2011 13:35:39
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,i,sum,maxim;
struct strada
{
    int d;
    int l;
};
strada x[50010];
bool comp(strada a,strada b)
{
    return a.d<=b.d;
}
int main()
{
    freopen("orase.in","r",stdin);
    freopen("orase.out","w",stdout);
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i].d,&x[i].l);
    }
    sort(x+1,x+n+1,comp);
    maxim=sum=x[1].l+x[2].d-x[1].d+x[2].l;
    for(i=2;i<=n;i++)
    {
        if(sum-x[i].l+x[i+1].d-x[i].d+x[i+1].l<x[i].l+x[i+1].d-x[i].d+x[i+1].l)
        {
            sum=x[i].l+x[i+1].d-x[i].d+x[i+1].l;
        }
        else
        {
            sum=sum-x[i].l+x[i+1].d-x[i].d+x[i+1].l;
        }
        if(maxim<sum)
        {
            maxim=sum;
        }
    }
    printf("%d",maxim);
    return 0;
}