Cod sursa(job #592333)

Utilizator tiganu_dolarMancea Catalin tiganu_dolar Data 27 mai 2011 20:43:42
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define pi pair<int,int>
#define x first
#define y second
#define maxim(a,b) (a>b ? a : b)
#define NMAX 2011

int n,c,sol;
pi v[NMAX];
int cv[NMAX];

int main ()
{
    int i,j,am,last,s;
    
    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);
        cv[i]=v[i].y;
    }
    sort(cv+1,cv+n+1);
    sort(v+1,v+n+1);
    for(i=n;i>=1 && cv[i]>c;i--)
    {
        last=0;am=0;s=0;
        for(j=1;j<=n;j++)
        {
            if(v[j].y<cv[i])
                continue;
            if(!am)
            {
                am=1;
                s=cv[i]-c;
                last=v[j].x;
            }
            else
            {
                s+=cv[i]-c*(v[j].x-last);
                last=v[j].x;
            }
            if(s<=0)
                s=cv[i]-c;
            sol=maxim(sol,s);
        }
    }
    printf("%d\n",sol);
    return 0;
}