Cod sursa(job #886787)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 23 februarie 2013 11:53:04
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("carnati.in");
ofstream cout("carnati.out");

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 > best)
                best = now;
        }

    return best;
}

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

    cin>>N>>C;
    for (i = 1; i <= N; i ++)
        cin>>x[i].T>>x[i].P;
    x[0].T = x[0].P = -10;
    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));

    cout<<profit<<"\n";
    return 0;
}