Cod sursa(job #530074)

Utilizator david_raucaRauca Ioan David david_rauca Data 6 februarie 2011 19:34:41
Problema Orase Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<fstream>
#include<iomanip>
using namespace std;

ifstream fin("orase.in");
ofstream fout("orase.out");

struct distanta{
       int d, l;         
};

distanta a[50002];

int m, n;

void Read();
void Solve();

int main()
{
    Read();
    Solve();
    
    fin.close();
    fout.close();
    
    return 0;
}

bool sortat( distanta x, distanta y )
{
     return x.d < y.d;
}

void Read()
{
     fin >> m >> n;
     for( int i = 1; i <= n; ++i )
          fin >> a[i].d >> a[i].l;
}

void Solve()
{
     int max_drum = -999;
     
     sort( a+1, a+n+1, sortat );
     
     int dif = 0;
     
     for( int i = 1; i <= n; ++i )
     {
          if( dif + a[i].d + a[i].l > max_drum )   
              max_drum = dif + a[i].d + a[i].l;
          
          if( a[i].l - a[i].d > dif )
              dif = a[i].l - a[i].d;
     }
     
     fout << max_drum <<'\n';
}