Cod sursa(job #1309959)

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