Cod sursa(job #142723)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 25 februarie 2008 01:29:44
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int N,C,best;
vector < pair<int,int> > v;

int main()
{
    int i,j,x,y,minv,sum,a,p;
    
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    
    scanf("%d%d",&N,&C);
    
    minv = 100000000;
    
    for ( i = 1; i <= N; ++i )
    {
        scanf("%d%d",&x,&y),v.push_back(make_pair(x,y)); 
        if ( x < minv ) minv = x;
    }
    v.push_back(make_pair(minv-1,0));
    
    sort(v.begin(),v.end());
    
    best = v[0].second - C;
    
    for ( i = 1; i <= N; ++i )
    {   
        sum = 0; a = 0; p = 0;
        for ( j = 1; j <= N; ++j )
        {
            sum = sum - ( v[j].first - v[j-1].first ) * C + v[i].second * ( ( v[i].second <= v[j].second ) ? (1) : (0) );
            if ( p != 0 )
               best = max(best,sum-a+(v[p+1].first-v[p].first-1)*C);            
            else
               best = max(best,sum);
                
            if ( sum < a )
               a = sum,p=j;
        }
    }
    printf("%d\n",best);
    return 0;
}