Cod sursa(job #1905379)

Utilizator vladdy47Bucur Vlad Andrei vladdy47 Data 6 martie 2017 01:19:48
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
# include <bits/stdc++.h>

using namespace std;

const int Nmax = 2000 + 5;

struct da
{
    int cost, timp;
};
da a[Nmax];

int n, c, i, x, y, A, B, P, Cost, j, ans;

int cmp (da A, da B)
{
    return A.timp < B.timp;
}

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

    scanf("%d %d\n", &n, &c);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d\n", &x, &y);
        a[i].cost = y, a[i].timp = x;
    }

    sort(a + 1, a + n + 1, cmp);

    for (i = 1; i <= n; ++i)
    {
        B = -INT_MAX, Cost = a[i].cost;

        for (j = 1; j <= n; ++j)
        {

            if (a[j].cost >= Cost) P = Cost;
            else P = 0;

            A = max (B + P - (a[j].timp - a[j - 1].timp) * c, P - c);
            B = A;
            ans = max(ans, A);
        }
    }

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

    return 0;
}