Cod sursa(job #1773776)

Utilizator preda.andreiPreda Andrei preda.andrei Data 8 octombrie 2016 10:58:07
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

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

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

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

	int raspuns = 0;
	for (auto &c : clienti) {
		int pret = c.second;
		int profit = 0, pmax = 0;

		for (int i = 0; i < n; ++i) {
			int vanzari = (clienti[i].second >= pret) ? pret : 0;

			if (profit == 0) {
				profit = vanzari - salariu;
			} else {
				profit += vanzari - salariu * (clienti[i].first - clienti[i - 1].first);
				profit = max(profit, vanzari - salariu);
			}

			profit = max(profit, 0);
			pmax = max(pmax, profit);
		}

		raspuns = max(raspuns, pmax);
	}

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