Cod sursa(job #370108)

Utilizator drujbarultudorTudor Mihai Munteanu drujbarultudor Data 30 noiembrie 2009 10:48:11
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int o,n,c,i,maxxx;
struct client
{
    int a,b;
};
client a[1000];
bool comp(client x,client y)
{
    return x.a<y.a;
}
int f(int p)
{
    int k,t,j,maxx;
    k=0;
    t=a[1].a;
    if (a[1].b>=p)
        k=p-c;
    else
        k=-c;
    maxx=k;
    for (j=2;j<=n;j++)
    {
        k=k-(a[j].a-a[j-1].a-1)*c;
        if (k<0) k=0;
        if (a[j].b>=p) k=k+p-c;
        else k=k-c;
        if (k>maxx)
            maxx=k;
    }
    return maxx;
}
int main ()
{
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    scanf ("%d%d",&n,&c);
    for (i=1;i<=n;i++)
        scanf ("%d%d",&a[i].a,&a[i].b);
    sort(a+1,a+n+1,comp);
    for (i=1;i<=n;i++)
    {
        o=f(a[i].b);
        //printf("pret=%d profit=%d\n",a[i].b,o);
        if (o>maxxx) maxxx=o;
    }
    printf("%d",maxxx);
    return 0;
}