Cod sursa(job #1199519)
Utilizator | Data | 19 iunie 2014 16:34:30 | |
---|---|---|---|
Problema | Carnati | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.78 kb |
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("carnati.in");
ofstream cout("carnati.out");
long long n,i,a,b,j,pivot,pret,start,aux,plata,finish,profit,ora,Pbest(-99999999),cumparatori(1),T[10000],P[10000];
int main()
{
cin>>n>>plata;
for (i=1;i<=n;++i) cin>>T[i]>>P[i];
Pbest=P[1]-plata;
start=T[1];
finish=T[1];
pret=P[1];
for (i=2;i<=n;++i){
cin>>T[i]>>P[i];
if (P[i]>pret) ++cumparatori;
Pbest=max(Pbest,cumparatori*pret-(T[i]-start+1)*plata);
Pbest=max(P[i]-plata,Pbest);
if (P[i]-plata == Pbest) {
start=T[i];
pret=P[i];
cumparatori=1;
}
aux=1;
for (j=i-1;j>=1;--j) {
if (P[j]>=P[i]) ++aux;
Pbest=max(aux*P[i]-(T[i]-T[j]+1)*plata,Pbest);
if (aux*P[i]-(T[i]-T[j]+1)*plata == Pbest ) {
pret=P[i];
cumparatori=aux;
start=T[j];
}
}
}
cout<<Pbest<<"\n";
return 0;
}