Cod sursa(job #1309963)

Utilizator Darius15Darius Pop Darius15 Data 6 ianuarie 2015 11:15:11
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("carnati.in");
ofstream g("carnati.out");
struct poz{long long t,p;};
poz a[2001];
bool cmp(poz a,poz b)
{
    return a.t<b.t;
}
long long d[2001],MAX,j,n,c,i;
int main()
{
   f>>n>>c;
   for (i=1;i<=n;i++)
    f>>a[i].t>>a[i].p;
   sort(a+1,a+n+1,cmp);
   MAX=0;
   for (i=1;i<=n;i++)
   {
       for (j=1;j<=n;j++)
        d[j]=0;
       for (j=1;j<=n;j++)
       {
           if (a[j].p>=a[i].p)
            if (a[i].p-c>d[j-1]+a[i].p-(a[j].t-a[j-1].t)*c)
               d[j]=a[i].p-c;
               else  d[j]=d[j-1]+a[i].p-(a[j].t-a[j-1].t)*c;
           else
            if (d[j-1]-(a[j].t-a[j-1].t)*c>0)
                d[j]=d[j-1]-(a[j].t-a[j-1].t)*c;
            else d[j]=0;
           MAX=max(d[j],MAX);
       }
   }
   g<<MAX;
    return 0;
}