Pagini recente » Cod sursa (job #2822230) | Cod sursa (job #600474) | Cod sursa (job #852516) | Cod sursa (job #496515) | Cod sursa (job #599783)
Cod sursa(job #599783)
#include<stdio.h>
#define MaxN 2100
#define ll long long
#define maximul MaxPrice[i-1] - (Timp[i] - Timp[i-1]) * C + Max[i-1]
int Price[MaxN];
int Timp[MaxN];
ll MaxPrice[MaxN];
ll Max[MaxN];
int MaxTimp[MaxN];
int B[MaxN];
int N;
int C;
ll MAX;
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",&Timp[i],&Price[i]);
for(int i=1;i<=N;i++)
{
Max[i] = Price[i] - C;
MaxPrice[i] = Price[i];
MaxTimp[i] = 1;
B[i] = 1;
if(MaxPrice[i-1] - (Timp[i] - Timp[i-1]) * 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] + Timp[i] - Timp[i-1];
}
if(Max[i-1] - (Timp[i] - Timp[i-1]) * C > Max[i] && MaxPrice[i] < MaxPrice[i-1])
{
MaxPrice[i] = MaxPrice[i-1];
Max[i] = Max[i-1] - (Timp[i] - Timp[i-1]) * C;
B[i] = B[i-1];
MaxTimp[i] = MaxTimp[i-1] + Timp[i] - Timp[i-1];
}
if(MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + Timp[i] - Timp[i-1]) > Max[i] && MaxPrice[i] < MaxPrice[i-1])
{
Max[i] = MaxPrice[i] * (B[i-1] + 1) - C * (MaxTimp[i-1] + Timp[i] - Timp[i-1]);
B[i] = B[i-1];
MaxTimp[i] = MaxTimp[i-1] + Timp[i] - Timp[i-1];
}
}
for(int i=1;i<=N;i++)
if(MAX < Max[i])
MAX = Max[i];
fprintf(g,"%llu ",MAX);
fclose(g);
fclose(f);
return 0;
}