Cod sursa(job #196582)

Utilizator alexeiIacob Radu alexei Data 27 iunie 2008 12:39:05
Problema Carnati Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
//bla bla bla
#define nmax 2024

typedef struct{
        int cost,timp;
        }q;
q v[nmax];

inline int cmp(q A,q B)
{
      if( A.cost==B.cost )
      return A.timp<B.timp;
      
      return A.cost<B.cost;
}

inline int max(const int a,const int b)
{
       if( a>b )
       return a;
       return b;
}

int main()
{
 freopen("carnati.in","r",stdin);
 freopen("carnati.out","w",stdout);
 
 int N,U;   
    
 scanf("%d%d",&N,&U);
 
 int i,j,a1,a2,a3=0;
    
 for(i=1; i<=N; ++i){
    scanf("%d%d",&a2,&a1);
    if( a1>U ){
    v[i-a3].cost=a1;
    v[i-a3].timp=a2;}
    else
    ++a3;
 }
 N-=a3;
 sort(v+1,v+N+1,cmp);
  
 int tmin,tmax,solfin=0,sum,sol;    
 int temp,aux=0,aux2,tcost;
 int space;
 
 for(i=1; i<=N; ++i)
 {         
          tmin=tmax=v[i].timp;
          tcost=v[i].cost;
          sol=v[i].cost-U;
          sum=1;
          temp=1;
          space=0;
          for(j=i+1; j<=N; ++j)
          {          
                     aux=0;
                     if( v[j].timp > tmax )
                     aux=v[j].timp-tmax,space=1;        
                     if( v[j].timp < tmin )
                     aux=tmin-v[j].timp,space=2;
                     aux2=(sum+1)*tcost-(temp+aux)*U;   
                     
                     if(  aux2 > sol )
                     {
                     sol=aux2;
                     ++sum;
                     temp+=aux;
                     if( space==1 )
                     tmax=v[j].timp;
                     else
                     if( space==2 )
                     tmin=v[j].timp;
                     }
                     space=0;
          }
          
          for(j=i-1; j>=1 && v[j].cost==tcost; --j)
          {          
                     aux=0;
                     if( v[j].timp > tmax )
                     aux=v[j].timp-tmax,space=1;        
                     if( v[j].timp < tmin )
                     aux=tmin-v[j].timp,space=2;
                     aux2=(sum+1)*tcost-(temp+aux)*U;   
                     
                     if(  aux2 > sol )
                     {
                     sol=aux2;
                     ++sum;
                     temp+=aux;
                     if( space==1 )
                     tmax=v[j].timp;
                     else
                     if( space==2 )
                     tmin=v[j].timp;
                     }
                     space=0;
          }
         solfin=max(solfin,sol);                
 }
    printf("%d\n",solfin);
    
    return 0;
}