Pagini recente » Cod sursa (job #644230) | Cod sursa (job #1724371) | Cod sursa (job #1206169) | Cod sursa (job #2149309) | Cod sursa (job #1344329)
#include <iostream>
#include <stdio.h>
#include <algorithm>
FILE *f, *g;
int rez[50001];
using namespace std;
struct elem {
int a;
int b;
};
elem v[50001];
bool srt(elem x, elem y){
return x.a < y.a;
}
int main()
{ int m, n, i, ans;
f = fopen( "orase.in", "r" );
g = fopen( "orase.out", "w" );
fscanf( f, "%d%d", &m, &n );
for ( i = 1; i <= n; i++){
fscanf( f, "%d%d", &v[i].a, &v[i].b );
}
sort( v + 1, v + n + 1, srt);
rez[ 1 ] = v[ 1 ].b;
ans = 0;
for( int i = 2; i <= n; ++ i ) {
int x, y;
x = v[ i - 1 ].b + v[ i ].a - v[ i - 1 ].a + v[ i ].b;
y = rez[ i - 1 ] - v[ i - 1 ].b + v[ i ].a - v[ i - 1 ].a + v[ i ].b;
rez[ i ] = max( x, y );
ans = max( ans, rez[ i ] );
}
fprintf( g, "%d\n", ans );
fclose(f);
fclose(g);
return 0;
}
/*
sortez crescator dupa d-uri
voi retine in u indicele celui mai indepartat oras din stanga; initial u = 1 si incep de la 2
la fiecare pas nou i aleg cel mai indepartat oras din stanga lui i: u sau i-1
*/