Pagini recente » Cod sursa (job #1874316) | Cod sursa (job #2774806) | Cod sursa (job #220480) | Cod sursa (job #2137734) | Cod sursa (job #599786)
Cod sursa(job #599786)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define MaxN 2100
#define ll long long
#define maximul MaxPrice[i-1] - (A[i].Timp - A[i-1].Timp) * C + Max[i-1]
typedef struct
{
int Price;
int Timp;
} cump;
cump A[MaxN];
ll MaxPrice[MaxN];
ll Max[MaxN];
int MaxTimp[MaxN];
int B[MaxN];
int N;
int C;
ll MAX;
bool cmp(cump a,cump b)
{
return a.Timp < b.Timp;
}
int max(int a,int b)
{
return a>b ? a:b;
}
int main()
{
FILE *f = fopen("carnati.in","r");
FILE *g = fopen("carnati.out","w");
fscanf(f,"%d %d",&N,&C);
for(int i=1;i<=N;i++)
fscanf(f,"%d %d",&A[i].Timp,&A[i].Price);
sort(A+1,A+N+1,cmp);
for(int i=1;i<=N;i++)
{
Max[i] = A[i].Price - C;
MaxPrice[i] = A[i].Price;
MaxTimp[i] = 1;
B[i] = 1;
if(MaxPrice[i-1] - (A[i].Timp - A[i-1].Timp) * C + Max[i-1] > Max[i] && MaxPrice[i] >= MaxPrice[i-1])
{
MaxPrice[i] = MaxPrice[i-1];
Max[i] = maximul;
B[i] = B[i-1] + 1;
MaxTimp[i] = MaxTimp[i-1] + A[i].Timp - A[i-1].Timp;
}
if(Max[i-1] - (A[i].Timp - A[i-1].Timp) * C > Max[i] && MaxPrice[i] < MaxPrice[i-1])
{
MaxPrice[i] = MaxPrice[i-1];
Max[i] = Max[i-1] - (A[i].Timp - A[i-1].Timp) * C;
B[i] = B[i-1];
MaxTimp[i] = MaxTimp[i-1] + A[i].Timp - A[i-1].Timp;
}
if(MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + A[i].Timp - A[i-1].Timp) > Max[i] && MaxPrice[i] < MaxPrice[i-1])
{
Max[i] = MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + A[i].Timp - A[i-1].Timp);
B[i] = B[i-1];
MaxTimp[i] = MaxTimp[i-1] + A[i].Timp - A[i-1].Timp;
}
}
for(int i=1;i<=N;i++)
if(MAX < Max[i])
MAX = Max[i];
fprintf(g,"%llu ",MAX);
fclose(g);
fclose(f);
return 0;
}