Cod sursa(job #223416)

Utilizator Mishu91Andrei Misarca Mishu91 Data 28 noiembrie 2008 16:45:23
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAX_N 2005

struct client{int t, p;} V[MAX_N];
int N, C;
long long Bst[MAX_N], Max, M;

void citire()
{
    scanf("%d %d",&N, &C);

    for(int i = 1; i <= N; ++i)
        scanf("%d %d",&V[i].t, &V[i].p);
}

struct cmp
{
    bool operator()(const client a, const client b) const
    {
        return(a.t < b.t);
    }
};

void solve()
{
    sort(V+1, V+N+1, cmp());

    Bst[0] = V[0].t = V[0].p = -10;
    for(int i = 1; i <= N; ++i)
    {
        int X = V[i].p, lst = 0;
        M = 0;

        for(int i = 1; i <= N; ++i)
        {
            if(V[i].p < X) {Bst[i] = 0; continue;}
            Bst[i] = X - C;
            long long plus = (long long) M + X;
            long long minus = (long long) C*(V[i].t - V[lst].t);
            long long k = plus - minus;
            if(k > Bst[i])
            {
                Bst[i] = k;
                lst = i;
            }
            else
                lst = i;
            M = Bst[i];
            if(M > Max)
                Max = M;
        }
   }

   printf("%lld\n", Max);
}

int main()
{
    freopen("carnati.in","rt",stdin);
    freopen("carnati.out","wt",stdout);

    citire();
    solve();
}