Cod sursa(job #832701)

Utilizator cldmeClaudiu Ion cldme Data 11 decembrie 2012 08:51:21
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
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;
}

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);
    }
    for(i=1;i<=n;i++)
    {
        pr=profit(v[i].p);
        if(pr>pmax) pmax=pr;
    }
    printf("%d",pmax);
    return 0;
}