Nu aveti permisiuni pentru a descarca fisierul grader_test13.in
Cod sursa(job #1344329)
| Utilizator | Data | 16 februarie 2015 17:25:55 | |
|---|---|---|---|
| Problema | Orase | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.08 kb |
#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
*/
