Pagini recente » Cod sursa (job #1380488) | Cod sursa (job #2605668) | Cod sursa (job #550637) | Cod sursa (job #386451) | Cod sursa (job #2197298)
#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;
}