Cod sursa(job #142724)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 25 februarie 2008 01:39:41
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define pb push_back
#define mp make_pair

using namespace std;

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

int main()
{
    int i,j,x,y,sum,a,p;
    
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    
    scanf("%d%d",&N,&C);
    
    v.pb(mp(-1,0));
    
    for ( i = 1; i <= N; ++i )
        scanf("%d%d",&x,&y),v.pb(mp(x,y)); 

    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 )
               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;
}