Cod sursa(job #1985022)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 26 mai 2017 18:05:30
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");
int n,i,j,timp,cost,d[2001],maxim;
pair<int,int>v[2001];
int main(){
    in >> n >> timp;
    for( i = 1; i <= n; i ++ ){
        in >> v[i].first>>v[i].second;
    }
    sort( v + 1, v + n + 1 );
    for( i = 1; i <= n; i ++ ){
        cost = v[i].second;
        for( j = 1; j <= n; j ++ ){
            d[j] = 0;
        }
        for( j = 1; j <= n; j ++ ){
            if( d[j-1] - (v[j].first- v[j-1].first)*timp > -timp ){
                d[j] = d[j-1]- (v[j].first- v[j-1].first)*timp ;
                if( v[j].second >= cost ){
                    d[j]+=cost;
                }
            }
            else{
                if( v[j].second >= cost ){
                    d[j]+=cost;
                    d[j]-=timp;
                }
                else{
                    d[j] = -timp;
                }
            }
            if( d[j] > maxim ){
                maxim = d[j];
            }
        }
    }
    out << maxim;
    return 0;
}