Cod sursa(job #1743966)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 19 august 2016 01:03:13
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
# include <stdio.h>
# include <stdlib.h>

# include <algorithm>

# define MAX_N 20000

using namespace std;

struct client {
    int t, p;
} v[1 + MAX_N];

int n, c;

bool cmp_t( client a, client b ) {
    return a.t <= b.t;
}

int S[1 + MAX_N];
int profit( int p ) {
    int i, b;
    b = 0;
    for ( i = 1; i <= n; i ++ )
        b = max( b, S[i] = ( p * ( v[i].p >= p ) + max( 0, S[i - 1] - c * ( v[i].t - v[i - 1].t ) ) ) );
    return max( b - c, 0 );
}

int main() {
    FILE *fin = fopen( "carnati.in", "r" ), *fout = fopen( "carnati.out", "w" );

    int i, max, r, d;

    fscanf( fin, "%d%d", &n, &c );

    for ( i = 1; i <= n; i ++ )
        fscanf( fin, "%d%d", &v[i].t, &v[i].p );

    sort( v + 1, v + n + 1, cmp_t );
    v[0].t = v[1].t;

    max = 0;
    for ( i = 1; i <= n; i ++ ) {
        r = profit( v[i].p );
        if ( r > max )
            max = r;
    }

    fprintf( fout, "%d", max );

    fclose( fin );
    fclose( fout );

    return 0;
}