Cod sursa(job #652424)

Utilizator idomiralinIdomir Alin idomiralin Data 24 decembrie 2011 13:56:41
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
# include <cstdio>
# include <algorithm>

using namespace std;

struct camp
{
       int d, l;
       }a[50005];

int cmp(camp a, camp b)
{
    if (a.d == b.d)
         return a.l > b.l;
    else return a.d < b.d;
}   
  
int m, n, dist, lung, dist1, i;  
int main()
{int max;
    
    freopen("orase.in","r",stdin);
    freopen("orase.out","w",stdout);
    
    scanf("%d%d",&m,&n);
    
    for (i = 1; i <= n; i++)
        scanf("%d%d",&a[i].d,&a[i].l);
    
    sort(a + 1, a + n + 1, cmp);
    
    dist = a[1].d;
    lung = a[1].l;
    max = 0;
    for (i = 2; i <= n; i++)
    {
        dist1 = lung + a[i].d - dist;
        if (dist1 + a[i].l > max)
                  max = dist1 + a[i].l;
                  
        if (dist1 < a[i].l)
        {
                  dist = a[i].d;
                  lung = a[i].l;
                  }
        }
        
    printf("%d",max);
    
return 0;
}