Cod sursa(job #2655185)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 3 octombrie 2020 15:19:03
Problema Carnati Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int NMAX = 2000;
pair <int, int> v[1 + NMAX];

bool functie(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.first < b.first;
}

int main()
{
    ifstream in("carnati.in");
    ofstream out("carnati.out");
    int n, c;
    int maxim = 0;

    in >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        in >> v[i].first >> v[i].second;
    }

    sort(v + 1, v + 1 + n, functie);

    for (int i = 1; i <= n; i++)
    {
        int pret_fixat = v[i].second;
        int sum_max = 0;
        int sum_crt = 0;

        int timp_ant = -1;

        for (int j = 1; j <= n; j++)
        {
            if (v[j].second >= pret_fixat)
            {
                if (timp_ant == -1)
                {
                    sum_crt = sum_crt + pret_fixat - c;
                }
                else
                {
                    sum_crt = sum_crt + pret_fixat - (v[j].first - timp_ant) * c;
                }
                timp_ant = v[j].first;
            }

            if (sum_crt > sum_max)
            {
                sum_max = sum_crt;
            }

            if (sum_crt < 0)
            {
                sum_crt = 0;
                timp_ant = -1;
                j--;
            }
        }

        if (sum_max > maxim)
        {
            maxim = sum_max;
        }
    }

    out << maxim << '\n';

    return 0;
}