Cod sursa(job #2197298)

Utilizator RaduIonescuRadu Ionescu RaduIonescu Data 21 aprilie 2018 17:39:26
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct client{
    int ora;
    int bani;
};

client vcl[2007];

int n,cost;

bool comp(client a,client b)
{
    return (a.ora<b.ora);
}

long long profit(int index)
{
    long long costactual=vcl[index].bani,i,j;
    long long intretinere,venit=0;
    long long bestProfitDreapta,bestProfitStanga;
    bestProfitDreapta = bestProfitStanga = -1500000000001LL;

    for (i=index+1;i<n;++i)
    {
        intretinere=(vcl[i].ora-vcl[index].ora)*cost;

        if (vcl[i].bani>=costactual) venit+=costactual;

        long long profit=venit-intretinere;
        //cout<<"  ora="<<vcl[i].ora<<", profit="<<profit<<"\n";
        bestProfitDreapta = max(bestProfitDreapta, profit);
    }

    venit=0;

    for (i=index-1;i>-1;--i)
    {
        intretinere=-((vcl[i].ora-vcl[index].ora)*cost);

        if (vcl[i].bani>=costactual) venit+=costactual;

        long long profit=venit-intretinere;
        bestProfitStanga = max(bestProfitStanga, profit);
    }

    long long profitFinal = vcl[index].bani - cost;
    if(bestProfitDreapta > 0)
        profitFinal += bestProfitDreapta;
    if(bestProfitStanga > 0)
        profitFinal += bestProfitStanga;

    //cout<<"index = "<<index<<", bani = "<<vcl[index].bani<<", cost = "<<cost<<"\n"; cout<<"profit initial = "<<vcl[index].bani - cost<<"\n"; cout<<"bestProfitStanga = "<<bestProfitStanga<<"\n"; cout<<"bestProfitDreapta = "<<bestProfitDreapta<<"\n";

    return profitFinal;
}

int main()
{
    int i;

    in>>n>>cost;

    for (i=0;i<n;++i)
        in>>vcl[i].ora>>vcl[i].bani;

    sort (vcl,vcl+n,comp);

    //for (i=0;i<n;++i)   cout<<vcl[i].ora<<" "; cout<<"\n\n";

    long long profitMax = 0;
    //profit(2);
    for(int i=0; i<n && 1; ++i)
    {
        long long profitActual = profit(i);
        //cout<<"Profit final = "<<profitActual<<"\n";
        profitMax = max(profitMax, profitActual);
        //cout<<"\n";
    }

    //cout<<"\n\nProfit maxim final = ";
    out<<profitMax;

    return 0;
}