Cod sursa(job #828199)

Utilizator OlaruSabinOlaru Sabin OlaruSabin Data 3 decembrie 2012 13:03:48
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct structura
{
    int x;
    int y;
};
bool cmp(structura a,structura b)
{
    return a.x<b.x;
}
int n,c,i,pret,j,pe;
long long maxim,sum;
structura v[2001];
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",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    for(i=1; i<=n; i++)
    {
        pret=v[i].y;
        sum=0;
        for(j=1; j<=n; j++)
        {
            if(sum<0)
                {
                    pe=1;
                    sum=0;
                }
            if(v[j].y>=pret)
                sum+=pret;
            if(!pe)
                sum-=(v[j].x-v[j-1].x)*c;
            pe=0;
            if(sum>maxim)
                maxim=sum;
        }
    }
    printf("%lld",maxim-c);
}