Cod sursa(job #1755770)

Utilizator preda.andreiPreda Andrei preda.andrei Data 11 septembrie 2016 00:27:11
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 2001

struct Client
{
    int timp;
    int pret;
};

vector<Client> clienti;

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

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

    clienti.push_back({0, 0});

    for (int i = 1; i <= n; ++i) {
        int t, p;
        fin >> t >> p;
        clienti.push_back({t, p});
    }

    auto comp = [] (Client c1, Client c2) -> bool { return c1.timp < c2.timp; };
    sort(clienti.begin(), clienti.end(), comp);

    int profitMax = 0;
    for (int i = 1; i <= n; ++i) {
        int profit = 0;
        int start = 0;

        if (clienti[i].pret <= salariu)
            continue;

        for (int j = 1; j <= n; ++j) {
            int p = profit + ((clienti[j].pret >= clienti[i].pret) ? clienti[i].pret : 0);

            if (start == 0) {
                start = j;
                p -= salariu;
            }
            else {
                p -= salariu * (clienti[j].timp - clienti[j - 1].timp);
            }

            if (p > 0) {
                profit = p;
                profitMax = max(profitMax, profit);
            }
            else if (clienti[j].pret >= clienti[i].pret) {
                profit = clienti[i].pret - salariu;
                start = j;
            }
            else {
                profit = 0;
                start = 0;
            }
        }
    }

    fout << profitMax;
    return 0;
}