Cod sursa(job #2927880)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 21 octombrie 2022 18:41:59
Problema Carnati Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <climits>

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;
}