Pagini recente » Cod sursa (job #2893861) | Cod sursa (job #2944499) | Cod sursa (job #2301019) | Cod sursa (job #2182203) | Cod sursa (job #536976)
Cod sursa(job #536976)
#include <fstream.h>
#include <algorithm>
#define N 2001
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
struct C{
int t;
int p;
} client[N];
int n,c,best = -(1<<32);
void read(){
int i,j;
fin>>n>>c;
for (i=1; i<=n; i++)
fin>>client[i].t>>client[i].p;
}
int cmp(C x, C y){
return x.t < y.t;
}
void fixeaza(int start, int stop, int newP, int &pfixat, int &max){
int i,sum1=0;
if ( client[start].p >= newP)
sum1 += newP - c;
else
sum1 -= c;
for (i=start+1; i<=stop; i++)
if ( client[i].p >= newP)
sum1 += newP - (client[i].t-client[i-1].t)*c;
else
sum1 -= (client[i].t-client[i-1].t)*c;
if (newP >= pfixat)
max += pfixat - (client[stop].t - client[stop-1].t) * c;
else
max -= (client[stop].t - client[stop-1].t) * c;
if (sum1 > max){
max = sum1;
pfixat = newP;
}
}
void solve(){
int i,startIdx=1,pfixat = 1<<32,max = -(1<<32);
//max = client[1].p - c;
//pfixat = client[1].p;
for (i=1; i<=n; i++){
if (max > best) best = max;
fixeaza(startIdx,i,client[i].p,pfixat,max);
// if vechea suma calculata cu pretul nou este mai mica decat elementul curent
// atunci noua secventa incepe de la elementul curent
// altfel se adauga elementu curent a noua suma.
if ( max < client[i].p - c){
max = client[i].p - c;
startIdx = i;
}
}
}
int main(){
read();
sort(client,client+n,cmp);
solve();
/*for (int i=1; i<=n; i++)
fout<<client[i].t<<" ";*/
fout<<best;
return 0;
}