Cod sursa(job #844704)

Utilizator elfusFlorin Chirica elfus Data 29 decembrie 2012 18:40:44
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

struct carnat
{
    int T, P;
} x[2500];

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

inline bool comp(carnat A, carnat B)
{
    return A.T < B.T;
}

int solve(int N, int X, int C)
{
    int i, best = 0, now = 0;

    for (i = 1; i <= N; i ++)
        if (x[i].P < X)
            now = max(now - (x[i].T - x[i - 1].T) * C, -C);
        else
        {
            int ret = now + X - (x[i].T - x[i - 1].T) * C;
            now = X - C;
            now = max(ret, now);
            //if (now < 0)
            //    now = 0;
            if (now > best)
                best = now;
        }

    return best;
}

int main()
{
    int i, N, C;

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

    scanf("%d%d", &N, &C);
    for (i = 1; i <= N; i ++)
        scanf("%d%d", &x[i].T, &x[i].P);

    sort(x + 1, x + N + 1, comp);

    int profit = 0;

    for (i = 1; i <= N; i ++)
        profit = max(profit, solve(N, x[i].P, C));

    printf("%d", profit);
    return 0;
}