Cod sursa(job #2698221)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 21 ianuarie 2021 15:15:01
Problema Carnati Scor 100
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <stdio.h>
#define NMAXX 2000

struct om {
    int timp, pret;
} v[NMAXX];
int cmp( struct om i, struct om j ) {
    if ( i.timp < j.timp )
        return 1;
    else if ( i.timp > j.timp )
        return 2;
    return 0;
}
void sort( int begin, int end ) {
    int b = begin, e = end;
    struct om aux, pivot = v[(begin + end) / 2];
    while ( cmp( v[b], pivot ) == 1 )
        b++;
    while ( cmp( v[e], pivot ) == 2 )
        e--;
    while ( b < e ) {
        aux = v[b];
        v[b] = v[e];
        v[e] = aux;
        do
            b++;
        while ( cmp( v[b], pivot ) == 1 );
        do
            e--;
        while ( cmp( v[e], pivot ) == 2 );
    }
    if ( begin < e )
        sort( begin, e );
    if ( e + 1 < end )
        sort( e + 1, end );
}
int max( int a, int b ) {
    return a > b ? a : b;
}
int main() {
    FILE *fin, *fout;
    int n, c, profit, maxx, time, i, j, curent, price;
    fin = fopen( "carnati.in", "r" );
    fout = fopen( "carnati.out", "w" );
    fscanf( fin, "%d%d", &n, &c );
    for ( i = 0; i < n; i++ ) {
        fscanf( fin, "%d%d", &v[i].timp, &v[i].pret );
    }
    sort( 0, n - 1 );
    maxx = 0;
    for ( i = 0; i < n; i++ ) {
        price = v[i].pret;
        curent = 0;
        time = -1;
        for ( j = 0; j < n; j++ ) {
            if ( v[j].pret >= price ) {
                profit = max( curent + price - c * ( v[j].timp - time ), price - c );
                time = v[j].timp;
                maxx = max( maxx, profit );
                curent = profit;
            }
        }
    }
    fprintf( fout, "%d", maxx );
    fclose( fin );
    fclose( fout );
    return 0;
}