Cod sursa(job #300113)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 7 aprilie 2009 11:34:55
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct str
{
   long t,p;
}a[10010];

long N,nr;
long S,k,suma[10010],K;

void citire()
{
     freopen ("carnati.in","r",stdin);
     freopen ("carnati.out","w",stdout);
     scanf("%ld %ld",&N,&K);
     for (int i=0;i<N;i++)
          scanf("%ld %ld",&a[i].t,&a[i].p);
}

void maxim()
{
     long maxim=0,pret,poz;
     for (int l=0;l<N;l++)
     {
          S=0,poz=-1;
          pret=a[l].p;
          for (int i=0;i<N;i++)
          {
               if (poz==-1)
                    poz=a[i].t;
               if (a[i].p>=pret)
               {
                    S+=pret;
                    S-=(a[i].t-poz+1)*K;
                    poz=a[i].t+1;
               }
               else
               {
                    S-=(a[i].t-poz+1)*K;
                    poz=a[i].t+1;
               }
               if (S<=0)
               {
                    S=0;
                    poz=-1;
               }
               if (S>maxim)
                    maxim=S;
          }
     }
     printf ("%ld\n",maxim);
}


bool cmf(str a, str b)
{
     return a.t<b.t;
}

int main ()
{
   citire();
   sort(a,a+N,cmf);
   maxim();
   return 0;
}