Cod sursa(job #139033)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 19 februarie 2008 17:34:46
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <stdlib.h>
#define inf 2140000000

long n,c,i,j,t[2002],pret[2002],ind[2002];
long max,s,cost;

int comp2(const void * n1, const void * n2){
    return (t[*((long*)n1)]-t[*((long*)n2)]);
}
int comp1(const void * n1, const void * n2){
    return (pret[*((long*)n1)]-pret[*((long*)n2)]);
}

int main(){
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    
    scanf("%ld %ld",&n,&c);
    for (i=1;i<=n;i++){
        scanf("%ld %ld",&t[i],&pret[i]);
        ind[i]=i;
    }
    
    qsort(ind,n+1,sizeof(long),comp1);
    qsort(ind,n+1,sizeof(long),comp2);
    
    max=-inf;
    ind[0]=0;
    t[0]=t[ind[1]]-1;
    for (i=1;i<=n;i++){
        cost=pret[i];
        s=0;
        //max=-inf;
        for (j=1;j<=n;j++){
            if (s==0)
               s-=c;
            else s-=c*(t[ind[j]]-t[ind[j-1]]);
            
            if (cost<=pret[ind[j]])s+=cost;
            if (s>0){
               if (s>max)max=s;
            }
            else {if (s>max)max=s;s=0;}
        }
    }
    
    printf("%ld\n",max);
    
return 0;
}