Pagini recente » Cod sursa (job #16930) | Cod sursa (job #1921565) | Cod sursa (job #754252) | Cod sursa (job #55239) | Cod sursa (job #536958)
Cod sursa(job #536958)
#include <fstream.h>
#include <algorithm>
#define N 2001
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
struct C{
int t;
long long p;
} client[N];
long long 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, long long &pfixat, long long &max){
int i,sum1=0;
if ( client[start].p >= newP)
sum1 += newP - c;
else
sum1 -= c;
for (i=start+1; i<=stop+1; 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+1].t - client[stop].t) * c;
else
max -= (client[stop+1].t - client[stop].t) * c;
if (sum1 > max){
max = sum1;
pfixat = newP;
}
}
void solve(){
int i,startIdx=1;
long long pfixat = client[i].p,max = -(1<<32);
for (i=1; i<=n; i++){
fixeaza(startIdx,i-1,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;
}
if (max > best) best = max;
}
}
int main(){
read();
sort(client,client+n,cmp);
solve();
/*for (int i=1; i<=n; i++)
fout<<client[i].t<<" ";*/
fout<<best;
return 0;
}