Cod sursa(job #1456419)

Utilizator BLz0rDospra Cristian BLz0r Data 30 iunie 2015 17:42:01
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

#define Nmax 2002
#define inf INT_MAX

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

struct client{
    int timp, bani;
}v[Nmax], aux[Nmax];

bool cmp ( client A, client B ){
    return A.timp < B.timp;
}

int main(){

    int N, K, st = 1, dr = 1, maxx = -inf, sts, drs, sol = -inf;

    fscanf ( f, "%d%d", &N, &K );
    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%d%d", &v[i].timp, &v[i].bani );

    sort ( v + 1, v + N + 1, cmp );

    v[0].timp = v[1].timp;

    int sum;
    for ( int i = 1; i <= N; ++i ){

        maxx = -inf;
        st = dr = 1;
        sum = 0;

        for ( int j = 1; j <= N; ++j ){

            if ( v[j].bani >= v[i].bani )
                sum += v[i].bani;

            int pierdut = ( v[j].timp - v[st].timp + 1 ) * K;

            if ( sum - pierdut < 0 ){
                st = j+1;
                dr = j+1;
                sum = 0;
            }
            else
                dr = j;

            if ( sum - pierdut > maxx ){
                maxx = sum - pierdut;
                sts = st;
                drs = dr;
            }
        }
        sol = max ( sol, maxx );
    }

    fprintf ( g, "%d", sol );

    return 0;
}