Cod sursa(job #1777834)

Utilizator silkMarin Dragos silk Data 12 octombrie 2016 22:16:35
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <algorithm>
#define INF 1<<30
#define NMax 2000
#define mp make_pair
using namespace std;

pair<int, int> v[NMax+1];

int main(){
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);

    int i,j,N,C,T,x,y,ans=-INF,temp,cost,val,inc,ok;

    scanf("%d %d",&N,&C);
    for(i = 1; i <= N; ++i)
    {
        scanf("%d %d",&x,&y);
        v[i] = mp(x,y);
    }
    sort(v+1,v+N+1);

    for(i = 1; i <= N; ++i)
    {
        temp = 0;
        val = v[i].second;
        for(j = 1; j <= N; ++j)
        if( v[j].second >= val ) { ok = 0; break; }

        for(; j <= N; ++j)
        if( v[j].second >= val )
        {
            if( !ok ) { inc = v[j].first; ok = 1; }
            temp = temp + val;
            cost = ( v[j].first - inc + 1 ) * C;

            if( ans < temp - cost ) ans = temp - cost;
            if( temp - cost < 0 )
            {
                temp = val;
                cost = C;
                inc = v[j].first;
                if( ans < temp - cost ) ans = temp - cost;

                if( temp - cost < 0 ) temp = ok = 0;
            }
        }
    }


    printf("%d\n", ans);



return 0;
}