Pagini recente » Cod sursa (job #3130219) | Cod sursa (job #829517) | Cod sursa (job #3137257) | Cod sursa (job #3260932) | Cod sursa (job #2927881)
#include <fstream>
#include <climits>
#include <algorithm>
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
const int DIM = 2005;
int n, c;
int dp[DIM];
struct buyer {
int time, price;
} v[DIM];
bool cmp(buyer a, buyer b) {
if (a.time < b.time)
return true;
else if (a.time == b.time)
return a.price < b.price;
return false;
}
int main() {
fin >> n >> c;
for (int i = 1; i <= n; i++)
fin >> v[i].time >> v[i].price;
sort(v + 1, v + n + 1, cmp);
int maxProfit = INT_MIN;
for (int i = 1; i <= n; i++) {
int setPrice = v[i].price;
for (int j = 1; j <= n; j++) {
int income = 0;
if (v[j].price >= setPrice)
income = setPrice;
int cost = c * (v[j].time - v[j - 1].time);
dp[j] = max(dp[j - 1] + income - cost, income - c);
maxProfit = max(maxProfit, dp[j]);
}
}
fout << maxProfit;
return 0;
}