Cod sursa(job #1770596)

Utilizator preda.andreiPreda Andrei preda.andrei Data 4 octombrie 2016 17:22:54
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

int AflaProfit(const vector<pair<int, int>> &cl, int pret, int salariu)
{
    int smax = 0;
    int scur = 0;
    bool primul = true;

    for (int i = 1; i < cl.size(); ++i) {
        if (!primul) {
            if (cl[i].second >= pret)
                scur += pret;
            scur -= salariu * (cl[i].first - cl[i - 1].first);
        }

        if (scur <= 0) {
            if (cl[i].second >= pret && pret > salariu) {
                scur = pret - salariu;
                primul = false;
            }
            else {
                scur = 0;
                primul = true;
            }
        }

        smax = max(smax, scur);
    }

    return smax;
}

int main()
{
    ifstream fin("carnati.in");
    ofstream fout("carnati.out");

    int n, salariu;
    fin >> n >> salariu;

    vector<pair<int, int>> clienti(n + 1);
    for (int i = 1; i <= n; ++i)
        fin >> clienti[i].first >> clienti[i].second;
    sort(clienti.begin() + 1, clienti.end());

    int profit_max = 0;
    for (int i = 1; i <= n; ++i)
        profit_max = max(profit_max, AflaProfit(clienti, clienti[i].second, salariu));

    fout << profit_max << "\n";
    return 0;
}