Cod sursa(job #852475)

Utilizator stoicatheoFlirk Navok stoicatheo Data 11 ianuarie 2013 12:21:21
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
int const N=2001;
int n,c;
 
struct nr{
    int t,p;
};
nr v[N];
int profit(int pr)
{
    int i,u=-1,prmax=-1,prc;
    for(i=1;i<=n;i++)
    {
        if(v[i].p<pr) continue;
        if(u!=-1)
        {
            prc-=(v[i].t-v[u].t-1)*c;
            if(prc<0)
                prc=0;
        }
        else
            prc=0;
        u=i;
        prc+=pr-c;
        if(prc>prmax) prmax=prc;
    }
    return prmax;
}
 
bool cmp(nr x, nr y)
{
    return x.t<y.t;
}
 
int main()
{
    int pr,pmax=-1,i;
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    scanf("%d%d",&n,&c);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].t,&v[i].p);
    }
    sort(v+1,v+1+n,cmp);
    for(i=1;i<=n;i++)
    {
        pr=profit(v[i].p);
        if(pr>pmax) pmax=pr;
    }
    printf("%d",pmax);
    return 0;
}