Cod sursa(job #2071930)

Utilizator tgm000Tudor Mocioi tgm000 Data 21 noiembrie 2017 10:27:12
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<cstdio>
int t[2001],p[2001],prof[2001];
int main(){
   int n,c,i,j,maxp,maxst,maxdr;
   freopen("carnati.in","r",stdin);
   freopen("carnati.out","w",stdout);
   scanf("%d%d",&n,&c);
   for(i=1;i<=n;i++)
      scanf("%d%d",&t[i],&p[i]);
   maxp=0;
   for(i=1;i<=n;i++){
      prof[i]=0;
      maxst=0;
      for(j=i-1;j>=1;j--){
         prof[j]=prof[j+1];
         prof[j]-=(t[j+1]-t[j])*c;
         if(p[j]>=p[i])
            prof[j]+=p[i];
         if(prof[j]>maxst)
            maxst=prof[j];
      }
      maxdr=0;
      for(j=i+1;j<=n;j++){
         prof[j]=prof[j-1];
         prof[j]-=(t[j]-t[j-1])*c;
         if(p[j]>=p[i])
            prof[j]+=p[i];
         if(prof[j]>maxdr)
            maxdr=prof[j];
      }
      if(maxst+maxdr+p[i]-c>maxp)
         maxp=maxst+maxdr+p[i]-c;
   }
   printf("%d",maxp);
   return 0;
}