Cod sursa(job #1344329)

Utilizator VictorDumitrescuDumitrescu Victor VictorDumitrescu 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
*/