Cod sursa(job #1099387)

Utilizator mucenic_b101Bogdan Mucenic mucenic_b101 Data 5 februarie 2014 20:11:12
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>
#define MAXN 2001
using namespace std;

struct tip {
    int t, p;
};
tip v[MAXN];

bool sortare( tip a, tip b ) {
    if( a.t < b.t || ( a.t == b.t && a.p >= b.t ) )
        return true;
    return false;
}

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

    int n, c, profit, timp, maxprofit, price;

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

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

    sort( v, v + n, sortare );

    maxprofit = ( 1<<30 ) - 1;
    maxprofit *= -1;

    for( int i = 0 ; i < n ; ++i ) {
        price = v[i].p;
        profit = 0;
        timp = v[0].t-1;
        for( int i = 0 ; i < n ; ++i ) {
            if( v[i].p >= price )
                profit += price;
            profit -= ( c * ( v[i].t - timp ) );
            if( profit > maxprofit )
                maxprofit = profit;
            if( profit < 0 ) {
                profit = 0;
                timp = v[i+1].t-1;
            }
            else timp = v[i].t;
        }
    }

    fprintf( g, "%d\n", maxprofit );

    fclose( f );
    fclose( g );
    return 0;
}