Cod sursa(job #1216478)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 4 august 2014 17:31:28
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include<fstream>
#include<algorithm>

using namespace std;

ifstream fin( "carnati.in" );
ofstream fout( "carnati.out" );

const int nmax = 2000;
struct str{ int x, t; } v[ nmax + 1 ];

bool cmp( str a, str b ) {
    return ( a.t < b.t );
}
int main() {
    int n, c, sol, s, ii;
    fin>>n>>c;
    v[ 0 ].t = -1;
    for( int i = 1; i <= n; ++ i ) {
        fin>>v[ i ].t>>v[ i ].x;
    }
    sort( v + 1, v + n + 1, cmp );

    sol = 0;
    for( int i = 1; i <= n; ++ i ) {
        s = ii = 0;
        for( int j = 1; j <= n; ++ j ) {
            if ( v[ j ].x >= v[ i ].x ) {
                s -= c * ( v[ j ].t - v[ ii ].t - 1 );
                if ( s < 0 ) {
                    s = 0;
                }
                ii = j;
                s += v[ i ].x - c;
                if ( s > sol ) {
                    sol = s;
                }
            }
        }
    }
    fout<<sol<<'\n';
    fin.close();
    fout.close();
    return 0;
}